LeetCode_97_JumpGame


1. question: 跳跃游戏(中等)

给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/jump-game

示例 1:

1
2
3
输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2:

1
2
3
输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。

提示:

1
2
1 <= nums.length <= 3 * 104
0 <= nums[i] <= 105

2. answers

这道题,最开始想的是回溯法,一个个尝试。但是无论是从大到小尝试还是从小到大尝试,或者尽可能地接近距离差,都是超时。代码如下所示:

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
44
45
public class Solution_0097_03 {

public boolean doJump(int[] nums, int start) {

if(start == nums.length - 1) return true;

if(start > nums.length - 1) return false;

if(nums[start] == 0) return false;

// 计算二者的差值。如果差值是在当前取值的范围内,那么就取该值。
// 如果不在范围内(说明只能是差值大),那么就取该范围的最大值,尽可能地迈步子大一点。
int index = nums.length - 1 - start;
index = Math.min(index, nums[start]);

for (int i = index; i >= 1; i--) {

// 注意,下一个位置找不到,不代表本位置的下个选择也找不到。因此,只有下个位置找到了,才终止循环。
boolean tag = doJump(nums, start + i);

if(tag) return true;
}

// 如果在[1, nums[start]]范围内都没找到合适的,那么就说明是没有结果。此时也包括了nums[start] = 0的情况
return false;
}

public boolean canJump(int[] nums) {

return doJump(nums, 0);
}

public static void main(String[] args) {
System.out.println();

Solution_0097 s = new Solution_0097();

int[] nums = {2, 3, 1, 1, 4};
// int[] nums = {3, 2, 1, 0, 4};
// int[] nums = {2, 0, 0};
// int[] nums = {2, 0};

System.out.println(s.canJump(nums));
}
}

参考题解,其实不需要到底纠结走哪几步,只需要判断是否在范围之内即可。

可以想象,从第0个位置开始,具有一定的能量,迈一步减少一个能量,但是到达该位置后,可以获得一定的能量。

因此,此刻的能量就是前一步的剩余能量和当前步的初始能量的最大值为什么是最大值呢?因为本来就是选择,可迈可不迈,所以,肯定要取最优情况。

只需要遍历每一步,如果当前的能量为0,说明不能迈了,走不到终点,返回false。如果当前能量能够到达终点,则返回true。如果当前还有能量,但小于距离差,所以继续遍历。

换种思路,其实从某个位置A一步迈到另一个位置C,一定等于经过中间某个位置B,再迈到另一个位置C。即一条路线,可分为若干个自路线。此时,上面的操作其实就是相当于将若干个路线合并了,即走一步,判断的是所有路线的同一个子路线并取最优解。

代码如下所示:

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
public class Solution_0097_04 {

public boolean canJump(int[] nums) {

if(nums.length == 1) return true;

// 假设初始值为1,即假设在头结点的前一个位置
int remain = 1;

// 注意,要到倒数第二个位置
for (int i = 0; i < nums.length - 1; i++) {

// 上一步到这一步,买了一步,因此 remain-1
remain = Math.max(remain - 1, nums[i]);

// 为0,表示永远也迈不出去,所以无需再遍历
if(remain == 0) return false;

if(remain >= nums.length - 1 - i) return true;
}

return false;
}

public static void main(String[] args) {
System.out.println();

Solution_0097_04 s = new Solution_0097_04();

// int[] nums = {2, 3, 1, 1, 4};
// int[] nums = {3, 2, 1, 0, 4};
// int[] nums = {2, 0, 0};
// int[] nums = {2, 0};
int[] nums = {0, 2, 3};

System.out.println(s.canJump(nums));
}
}

3. 备注

参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)代码随想录 (programmercarl.com)


文章作者: 浮云
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 浮云 !
  目录