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; }
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};
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;
int remain = 1;
for (int i = 0; i < nums.length - 1; i++) {
remain = Math.max(remain - 1, nums[i]);
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 = {0, 2, 3};
System.out.println(s.canJump(nums)); } }
|
3. 备注
参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com),代码随想录 (programmercarl.com)。