1. question: 跳跃游戏II（中等）
给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/jump-game-ii
示例 1:
1
2
3
4
| 输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
|
示例 2:
1
2
| 输入: nums = [2,3,0,1,4]
输出: 2
|
提示:
1
2
| 1 <= nums.length <= 104
0 <= nums[i] <= 1000
|
2. answers
这道题和跳跃游戏类似，只不过那道题是判断能否到达重点，即遍历每一点，计算允许的剩余步数（覆盖范围），如果是0，则不会。。。
而本道题则是肯定能够到达终点，计算最小跳数。仍然可以按照覆盖范围来做。
最直观的方法是在跳跃的时候，跳跃本次最远的那个，比如本元素是3，那么就直接跳3个位置。这显然是不对的，因为无法保证3那个位置是否是0，并且万一2那个位置比3那个位置的数大很多呢？
本质上是无法保证下一跳是否能够跳更远。因此，在本次跳跃的时候，不能简单地跳本次最远的那个，而是在本跳的范围内跳能够保证下次最远的那个，如此下去，每次都保证下一跳是最远的，这样就完美解决了上述的问题。并且循环，最终能够保证到达终点是最短的。
那么怎么计算跳跃次数呢？每次都遍历本跳的所有选择，计算下一跳的最远选择（选择本次跳多远），当到达本范围的最终点时，表明本范围选择完了，跳数加1（注意，这并不意味着是在本终点进行跳跃，只是表明选择了最优点，开始跳了）。因为最优点保证了下一跳的范围，即不一定是在本终点跳跃的。代码如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| public class Solution_0098 {
public int jump(int[] nums) {
int result = 0;
int end = 0;
int temp = 0;
for (int i = 0; i <= end && end < nums.length - 1; ++i) {
temp = Math.max(temp, i + nums[i]);
if (i == end) {
end = temp;
result++;
}
}
return result;
}
public static void main(String[] args) {
System.out.println();
int[] nums = {2, 3, 0, 1, 4};
Solution_0098 s = new Solution_0098();
System.out.println(s.jump(nums));
}
}
|
（上述是参考题解的），这是自己实现了一遍：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| public class Solution_0098_02 {
public int jump(int[] nums) {
int maxRange = 0;
int nextMaxRange = 0;
int jumpCount = 0;
for (int i = 0; i < nums.length; i++) {
if(maxRange >= nums.length - 1) break;
nextMaxRange = Math.max(nextMaxRange, i + nums[i]);
if(i == maxRange) {
maxRange = nextMaxRange;
jumpCount ++;
}
}
return jumpCount;
}
public static void main(String[] args) {
System.out.println();
int[] nums = {2, 3, 1, 1, 4};
Solution_0098_02 s = new Solution_0098_02();
System.out.println(s.jump(nums));
}
}
|
3. 备注
参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。
