You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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 reachnums[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^4
0 <= nums[i] <= 1000
It's guaranteed that you can reach nums[n - 1].
这题是之后那道 Jump Game 的延伸,那题是问能不能到达最后一个数字,而此题只让求到达最后一个位置的最少跳跃数,貌似是默认一定能到达最后位置的? 题目中说了起始位置在 nums[0],并且数组中的每个数字表示当前的跳力,即若 nums[i] 的位置上的数字是j,则可以跳跃的范围是 [i, i + j],当然 i+j 需要小于n,否则会越界。此题的核心方法是利用贪婪算法 Greedy 的思想来解,想想为什么呢? 为了较快的跳到末尾,想知道每一步能跳的范围,这里贪婪并不是要在能跳的范围中选跳力最远的那个位置,因为这样选下来不一定是最优解,这么一说感觉又有点不像贪婪算法了。
其实这里贪的是一个能到达的最远范围,遍历当前跳跃能到的所有位置,然后根据该位置上的跳力来预测下一步能跳到的最远距离,贪出一个最远的范围,一旦当这个范围到达末尾时,当前所用的步数一定是最小步数。需要两个变量 cur 和 pre 分别来保存当前的能到达的最远位置和之前能到达的最远位置,只要 cur 未达到最后一个位置则循环继续,pre 先赋值为 cur 的值,表示上一次循环后能到达的最远位置,如果当前位置i小于等于 pre,说明还是在上一跳能到达的范围内,根据当前位置加跳力来更新 cur,更新 cur 的方法是比较当前的 cur 和 i + nums[i] 之中的较大值,如果题目中未说明是否能到达末尾,还可以判断此时 pre 和 cur 是否相等,如果相等说明 cur 没有更新,即无法到达末尾位置,返回 -1,代码如下:
解法一:
class Solution {
public:
int jump(vector<int>& nums) {
int res = 0, n = nums.size(), i = 0, cur = 0;
while (cur < n - 1) {
++res;
int pre = cur;
for (; i <= pre; ++i) {
cur = max(cur, i + nums[i]);
}
if (pre == cur) return -1; // May not need this
}
return res;
}
};
还有一种写法,跟上面那解法略有不同,但是本质的思想还是一样的,关于此解法的详细分析可参见网友 实验室小纸贴校外版的博客,这里 cur 是当前能到达的最远位置,last 是上一步能到达的最远位置,遍历数组,首先用 i + nums[i] 更新 cur,这个在上面解法中讲过了,然后判断如果当前位置到达了 last,即上一步能到达的最远位置,说明需要再跳一次了,将 last 赋值为 cur,并且步数 res 自增1,这里小优化一下,判断如果 cur 到达末尾了,直接 break 掉即可,代码如下:
解法二:
class Solution {
public:
int jump(vector<int>& nums) {
int res = 0, n = nums.size(), last = 0, cur = 0;
for (int i = 0; i < n - 1; ++i) {
cur = max(cur, i + nums[i]);
if (i == last) {
last = cur;
++res;
if (cur >= n - 1) break;
}
}
return res;
}
};
请点击下方图片观看讲解视频
Click below image to watch YouTube Video
You are given a 0-indexed array of integers
nums
of lengthn
. You are initially positioned atnums[0]
.Each element
nums[i]
represents the maximum length of a forward jump from indexi
. In other words, if you are atnums[i]
, you can jump to anynums[i + j]
where:0 <= j <= nums[i]
andi + j < n
Return the minimum number of jumps to reach
nums[n - 1]
. The test cases are generated such that you can reachnums[n - 1]
.Example 1:
Example 2:
Constraints:
1 <= nums.length <= 10^4
0 <= nums[i] <= 1000
nums[n - 1]
.这题是之后那道 Jump Game 的延伸,那题是问能不能到达最后一个数字,而此题只让求到达最后一个位置的最少跳跃数,貌似是默认一定能到达最后位置的? 题目中说了起始位置在 nums[0],并且数组中的每个数字表示当前的跳力,即若 nums[i] 的位置上的数字是j,则可以跳跃的范围是 [i, i + j],当然 i+j 需要小于n,否则会越界。此题的核心方法是利用贪婪算法 Greedy 的思想来解,想想为什么呢? 为了较快的跳到末尾,想知道每一步能跳的范围,这里贪婪并不是要在能跳的范围中选跳力最远的那个位置,因为这样选下来不一定是最优解,这么一说感觉又有点不像贪婪算法了。
其实这里贪的是一个能到达的最远范围,遍历当前跳跃能到的所有位置,然后根据该位置上的跳力来预测下一步能跳到的最远距离,贪出一个最远的范围,一旦当这个范围到达末尾时,当前所用的步数一定是最小步数。需要两个变量 cur 和 pre 分别来保存当前的能到达的最远位置和之前能到达的最远位置,只要 cur 未达到最后一个位置则循环继续,pre 先赋值为 cur 的值,表示上一次循环后能到达的最远位置,如果当前位置i小于等于 pre,说明还是在上一跳能到达的范围内,根据当前位置加跳力来更新 cur,更新 cur 的方法是比较当前的 cur 和 i + nums[i] 之中的较大值,如果题目中未说明是否能到达末尾,还可以判断此时 pre 和 cur 是否相等,如果相等说明 cur 没有更新,即无法到达末尾位置,返回 -1,代码如下:
解法一:
还有一种写法,跟上面那解法略有不同,但是本质的思想还是一样的,关于此解法的详细分析可参见网友 实验室小纸贴校外版的博客,这里 cur 是当前能到达的最远位置,last 是上一步能到达的最远位置,遍历数组,首先用 i + nums[i] 更新 cur,这个在上面解法中讲过了,然后判断如果当前位置到达了 last,即上一步能到达的最远位置,说明需要再跳一次了,将 last 赋值为 cur,并且步数 res 自增1,这里小优化一下,判断如果 cur 到达末尾了,直接 break 掉即可,代码如下:
解法二:
Github 同步地址:
#45
类似题目:
Jump Game
Jump Game III
Jump Game IV
Jump Game V
Jump Game VIII
Minimum Number of Visited Cells in a Grid
Maximum Number of Jumps to Reach the Last Index
Visit Array Positions to Maximize Score
参考资料:
https://leetcode.com/problems/jump-game-ii/
https://leetcode.com/problems/jump-game-ii/discuss/18028/O(n)-BFS-solution
https://leetcode.com/problems/jump-game-ii/discuss/18023/Single-loop-simple-java-solution
LeetCode All in One 题目讲解汇总(持续更新中...)
(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,快快加入吧~)
微信打赏
Venmo 打赏
---|---
The text was updated successfully, but these errors were encountered: