LeetCode_97_JumpGame

LeetCode

发布日期: 2022-06-12

更新日期: 2022-06-12

文章字数: 1.1k

阅读时长: 4 分

阅读次数:

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

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

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。即一条路线，可分为若干个自路线。此时，上面的操作其实就是相当于将若干个路线合并了，即走一步，判断的是所有路线的同一个子路线并取最优解。

代码如下所示：

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));
    }
}