45.Jump Game II

tags: Medium,Array,DP,Greedy

45. Jump Game II

題目描述

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 <= 10⁴
• 0 <= nums[i] <= 1000

解答

Javascript

function jump(nums) {
  let max = 0;
  let jump = 0;
  let temp = 0;
  for (let i = 0; i < nums.length - 1; i++) {
    max = Math.max(max, i + nums[i]);
    if (i === temp) {
      jump++;
      temp = max;
    }
  }

  return jump;
}

Marsgoat Feb 8, 2023

C++

思路:

1. 計算從左走到右邊最小步數
2. BFS計算步數, 可想成第一輪可到達的點是index 0, 第二輪是第一輪可新到達的點, …, 當一輪新到達的點達終點即結束

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size()==1) return 0;
        int step = 1, start = 1, end = nums[0];
        while(end < nums.size()-1)
        {
            int next_round_start = end+1;
            int next_round_end = end;
            for(int i = start; i <= end; i++)
                next_round_end = max(next_round_end, i+nums[i]);

            start = next_round_start;
            end = next_round_end;

            step++;
        }
        return step;
    }
};

Time:

$O(n)$
Extra Space:

$O(1)$

XD Feb 8, 2023

Python

class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) == 1: return 0
        jumps, cur_end, cur_far = 0, 0, 0

        for i in range(len(nums) - 1):
            cur_far = max(cur_far, i + nums[i])
            if i == cur_end:
                cur_end = cur_far
                jumps += 1

        return jumps

Ron Chen Feb 9, 2023

Reference

回到題目列表