Jump Game II - LeetCode

https://leetcode.com/problems/jump-game-ii/?envType=study-plan-v2&envId=top-interview-150

LeetCode_Sharing.png

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

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

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

Constraints:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000
  • It’s guaranteed that you can reach nums[n - 1].

这里需要填写最少的步数。采用广度优先进行暴力计算。

思路：

  1. 初始化当前可到达的最远位置 farthest 为 0，初始化当前的跳跃结束位置 end 为 0，初始化跳跃次数 jumps 为 0。
  2. 遍历数组 nums。
  3. 对于每一个位置 i，更新 farthest 为 max(farthest, i + nums[i])。这是因为从位置 i 最多可以跳到 i + nums[i]。
  4. 如果 i 等于 end，这意味着我们已经达到了上一次跳跃的最远位置，所以我们需要再跳一次。这时，更新 jumps 并且设置 end 为 farthest。
  5. 重复上述步骤直到遍历完整个数组。
class Solution:
    def jump(self, nums: List[int]) -> int:
        if not nums or len(nums) == 1:
            return 0

        jumps, end, farthest = 0, 0, 0
        for i in range(len(nums) - 1):
            farthest = max(farthest, i + nums[i])
            if i == end:
                jumps += 1
                end = farthest

        return jumps

class Solution {
    public int jump(int[] nums) {
        int farthest = 0;
        int end = 0;
        int steps = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            farthest = farthest > i + nums[i] ? farthest : i + nums[i];
            if (i == end){
                steps += 1;
                end = farthest;
            }
        }
        return steps;
    }
}

class Solution {
public:
    int jump(vector<int>& nums) {
        int farthest = 0;
        int end = 0;
        int steps = 0;

        for (int i = 0; i < nums.size() - 1; ++i) {
            farthest = farthest > nums[i] + i ? farthest : nums[i] + i;
            if (i == end){
                steps ++;
                end = farthest;
            }
        }
        return steps;
    }
};