【leetcode.55 跳跃游戏】

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

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

该题判断，能否到达，因为是多个可选，因此只判断跳跃最远就可以了

例如index=0，最多跳2，即index 0~2均可达，这样只需要记录跳跃到每个位置之后，能到达的最大位置即可

这里有一个关键，到达每个位置后，如果某个位置不可能到达怎么办？那就通过一个判断条件来进行限制：

public class Solution {
    public boolean canJump(int[] nums) {
        int rightMax = 0;

        for (int i = 0; i < nums.length; i++) {
            // 能跳到i才做判断
            if (rightMax >= i) {
                // 能不能跳到位置x，即x之前任意一个位置n[i] + i >= x
                rightMax = Math.max(rightMax, nums[i] + i);
                if (nums[i] + i >= nums.length - 1) {
                    return true;
                }
            }

        }
        return false;
    }
}

【leetcode. 45跳跃游戏2】

给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：

0 <= j <= nums[i] 且
i + j < n

返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

这个题和跳跃游戏1相比，要记录每跳1步所能到达的最大值，即第m次跳跃，从m-2的索引开始遍历到m-1的索引，找nums[i] + i的最大值，填进去

比如跳0步，即最大到0；跳1步最大到3；跳2步，则遍历0~3，假如是5；跳3步，则遍历3~5，为什么呢，因为0~3位置最远跳到5，再遍历0~3也没有意义了，遍历没有找过的3~5，即第3步最远距离了

class Solution {
    public int jump(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        // 数组表示跳跃n次能到达的最大位置，题目说一定能到，那就组多跳n-1次
        int[] maxIndex = new int[nums.length + 1];
        maxIndex[0] = 0;
        maxIndex[1] = 0 + nums[0];
        if (maxIndex[1] >= nums.length - 1) {
            return 1;
        }
        // 第m次跳跃，从m-2的索引开始遍历到m-1的索引，找最大值，填进去
        for (int i = 2; i <= nums.length; i++) {
            for (int j = maxIndex[i - 2]; j <= maxIndex[i - 1]; j ++) {
                maxIndex[i] = Math.max(maxIndex[i], nums[j] + j);
                if (maxIndex[i] >= nums.length - 1) {
                    return i;
                }
            }
        }
        return nums.length - 1;

    }
}

当然，跳跃1也可以改成动态规划模式，即跳到某一个值后，最远距离不再增加，也是一种思路

目录CONTENT

贪心算法

【leetcode.55 跳跃游戏】

【leetcode. 45跳跃游戏2】

评论区