55. 跳跃游戏

LeetCode： 55. 跳跃游戏

贪心题

贪心解法

    // 直接更新可跳的最远的距离
    public boolean canJump(int[] nums) {
        int skip = 0;
        for (int i = 0; i < nums.length; i++) {
            if(i <= skip){
                // i <= skip 说明 i 可达
                skip = Math.max(skip, i + nums[i]);
                // 这里可以提前返回
                // if(skip >= nums.length)  return true;
            } else {
                // 不可达
                return false;
            }
        }
        return true;
    }

当 skip 大于 nums.length 时 ， 就可以在 for 里可以提前结束， 跳出循环

if(skip >= nums.length)  return true;

dl简化版解法

这题这种解法的思路太强了 强到我已经认不出来这是贪心写法了…

思路：
1，1，1，0，4，5

当一个 i 位置能到，那么左边的位置就全都能到了， 所以直接更新最远的距离挨着跳，不需要考虑 0 ， 不用想那么多。

即使跳到 0， 当 skip 大于当前 0 的下标 i， 一样是可达，继续遍历后面的数。当 skip == i, 并且 arr[i] == 0 ， 此时 skip 更新 max 不变，下次遍历 >> i + 1 >> skip = i >> skip < i + 1 >> 所以 i + 1 不可达 >> return false;

    public boolean canJump(int[] nums) {
        int k = 0;
        // 每次起跳更新能跳到的最远距离
        for (int i = 0; i < nums.length; i++) {
        	// 不可达  >>   false
            if(i > k) return false;
            k = Math.max(k, i + nums[i]);
        }
        return true;
    }

---

>> 解题思路

大佬思路：