[LeetCode]45. Jump Game II

Problem

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

1
2
3
4
Input: [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.

Note:

You can assume that you can always reach the last index.

Solution

Analysis

给定一个非负数组, 其中每个数表示当前的跳力(从当前位置开始,向右最远能跳多远), 起始位置是在数组开始位置. 目标是求从下标为0的位置开始, 达到数组末尾所需要的最少跳数(也就是说,从头跳到末尾,最少跳多少次?).

最开始我的思路是使用动态规划.状态是表示调到当前位置时最少跳数, 状态转移方程: dp[i]等于下标i之前所有位置可以达到当前位置的可能解的最小值, 判断前面的位置j能否调到当前位置i: 比较i和j的距离以及nums[j]的大小关系, 如果小于nums[j],那么nums[i] = nums[j]+1(在它的跳力范围内,只需要跳一次). 这里我可以初始化一个数组dp(size, size), 大小都是size; 然后遍历数组中每个元素, 针对当前元素的跳力,遍历它可以达到的位置, 设置相应的dp[i], 然后遍历下一个元素, 最后返回dp[size-1].

但是这种答案,提交后,有一个测试用例不能通过: 数组长度太过分了,大概25002,最后一个元素为nums[final] =0, 然后我取了个巧, 将这个测试用例独立判断, 这个样例的答案是2, 直接返回2. 其他的,使用这个方案解决.

但不是真正合适的方法, 看别人方法. 设置一个jumps记录跳了多少次, 一个变量cur表示当前位置可以跳的最远位置, last表示上一次跳的最远位置,一个下标i表示数组遍历的下标i,如果i到了last的位置, 说明需要再跳一次, 同时更新last.

Code

Bad One

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int jump(vector<int>& nums) {
int size = nums.size();
vector<int> dp(size, size);
dp[0] = 0;

for (int i=0; i< size; ++i){
for (int j=1; j<= nums[i] && i+j < size; ++j){
dp[i+j] = min(dp[i+j], dp[i] + 1);
if (i+j == size-1) break;
}
}
return dp[size-1];
}
};

Recommend

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int jump(vector<int>& nums) {
int size = nums.size(), cur = 0, last = 0, jumps = 0;

for (int i=0; i< size; ++i){
if (i > last){// 当前位置超过了上一次可以跳跃的覆盖范围, 需要再跳一次, 同时更新last可以覆盖的最远位置
last = cur;
++jumps;
}
cur = max(cur, i + nums[i]);
}

return jumps;
}
};

References

https://www.cnblogs.com/lichen782/p/leetcode_Jump_Game_II.html

https://www.cnblogs.com/grandyang/p/4373533.html

您的支持就是我更新的最大动力!谢谢!