题解

题面描述

给定一个长度为 $n$ 的 $0$ 索引整数数组 $nums$。初始位置为 $nums[0]$。
每个元素 $nums[i]$ 表示从索引 $i$ 向后跳转的最大长度。换句话说，如果你在 $nums[i]$ 处，你可以跳转到任意 $nums[i+j]$ 处，其中 $0 \\leq j \\leq nums[i]$ 且 $i+j<n$。
返回到达 $nums[n-1]$ 的最小跳跃次数。题目保证可以到达 $nums[n-1]$。

思路

采用贪心算法：

• 使用两个变量：$end$ 表示当前跳跃能到达的最远边界，$maxReach$ 表示遍历过程中能跳跃到的最远位置。
• 当遍历到当前边界时，说明需要跳跃一次，将跳跃次数加 $1$，并更新边界为 $maxReach$。
• 遍历过程中不断更新 $maxReach = \\max(maxReach, i+nums[i])$。
• 当边界达到或超过 $n-1$ 时，即可得到最小跳跃次数。

代码分析

• 贪心策略本质：每次尽可能向前跳，使得在下一步中能够覆盖最大的范围，从而达到最少跳跃次数。
• 时间复杂度：$O(n)$，只需要遍历数组一次。
• 空间复杂度：$O(1)$，只使用常数空间。

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    // 函数 jump 返回到达最后一个位置的最小跳跃次数
    int jump(vector<int>& nums) {
        int n = nums.size();
        // 如果数组大小为 1，则不需要跳跃
        if(n < 2) return 0;
        int jumps = 0;      // 跳跃次数
        int maxReach = 0;   // 当前能到达的最远位置
        int end = 0;        // 当前跳跃的边界
        for (int i = 0; i < n - 1; i++) {
            maxReach = max(maxReach, i + nums[i]); // 更新最大能到达的位置
            // 当遍历到当前边界时，需要跳跃一次
            if (i == end) {
                jumps++;
                end = maxReach;
            }
        }
        return jumps;
    }
};

int main(){
    vector<int> nums;
    int num;
    // 读取一行输入，直到输入结束
    while(cin >> num) {
        nums.push_back(num);
    }
    Solution sol;
    cout << sol.jump(nums) << endl;
    return 0;
}

Python

# 定义 Solution 类，包含 jump 方法
class Solution:
    def jump(self, nums):
        # 获取数组长度
        n = len(nums)
        # 如果数组长度小于 2，则不需要跳跃
        if n < 2:
            return 0
        jumps = 0         # 跳跃次数
        maxReach = 0      # 当前能到达的最远位置
        end = 0           # 当前跳跃的边界
        # 遍历数组，不包括最后一个位置
        for i in range(n - 1):
            # 更新最大能到达的位置
            maxReach = max(maxReach, i + nums[i])
            # 当到达当前边界时，需要进行一次跳跃
            if i == end:
                jumps += 1
                end = maxReach
        return jumps

if __name__ == "__main__":
    # 从标准输入读取一行数据，分割成整数列表
    import sys
    nums = list(map(int, sys.stdin.read().strip().split()))
    sol = Solution()
    print(sol.jump(nums))

Java

import java.util.*;
import java.io.*;

public class Main {
    // 定义 Solution 类，包含 jump 方法
    static class Solution {
        // 方法 jump 返回到达最后一个位置的最小跳跃次数
        public int jump(int[] nums) {
            int n = nums.length;
            // 如果数组长度小于 2，则不需要跳跃
            if(n < 2) return 0;
            int jumps = 0;    // 跳跃次数
            int maxReach = 0; // 当前能到达的最远位置
            int end = 0;      // 当前跳跃的边界
            // 遍历数组，不包括最后一个位置
            for (int i = 0; i < n - 1; i++) {
                // 更新最大能到达的位置
                maxReach = Math.max(maxReach, i + nums[i]);
                // 当到达当前边界时，需要进行一次跳跃
                if (i == end) {
                    jumps++;
                    end = maxReach;
                }
            }
            return jumps;
        }
    }
    
    public static void main(String[] args) throws IOException {
        // 使用 Scanner 读取标准输入
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList<>();
        // 逐个读取整数
        while(sc.hasNextInt()){
            list.add(sc.nextInt());
        }
        int[] nums = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            nums[i] = list.get(i);
        }
        Solution sol = new Solution();
        // 输出结果到标准输出
        System.out.println(sol.jump(nums));
        sc.close();
    }
}

Leetcode 79.跳跃游戏Ⅱ-原题链接

题目内容

给定一个长度为 $n$的 $0$ 索引整数数组 $nums$。初始位置为 $nums[0]$。

每个元素 $nums[i]$ 表示从索引 $i$ 向后跳转的最大长度。换句话说，如果你在 $nums[i]$ 处，你可以跳转到任意 $nums[i + j]$ 处:

• $0 <= j <= nums[i]$
• $i + j < n$

返回到达 $nums[n - 1]$的最小跳跃次数。生成的测试用例可以到达 $nums[n - 1]$。

输入描述

输入一个数组

输出描述

输出一个整数表示最小跳跃次数

样例1

输入

2 3 1 1 4

输出

2

说明

跳到最后一个位置的最小跳跃数是 $2$。

从下标为 $0$ 跳到下标为 $1$ 的位置，跳 $1$ 步，然后跳$3$步到达数组的最后一个位置。

样例2

输入

2 3 0 1 4

输出

2

提示：

• $1 <= nums.length <= 10^4$
• $0 <= nums[i] <= 1000$
• 题目保证可以到达 $nums[n-1]$