HackMD
45.Jump Game II
tags: Medium,Array,DP,Greedy
題目描述
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
解答
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++
思路:
- 計算從左走到右邊最小步數
- 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:
Extra Space:
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
