跳跃游戏

跳跃游戏

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

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

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

示例

示例1:

输入: nums = [2,3,1,1,4]

输出: true

示例2:

输入: nums = [3,2,1,0,4]

输出: false

思路

刚看到这个题可能会去思考怎样从数组去规划路线，在哪个位置跳几步才是最好的。这样想的话是把这个问题想复杂了，我们只需要知道是否能跳到终点，路线不是我们关心的。如何知道是否能跳到终点呢？关键在于每次跳跃的时候必须保证之前能跳到这个位置，所以我们遍历数组，每次都更新最远能跳到的位置，如果遍历到大于可达最远位置的元素，那么就不能到达终点。如果可达最远位置大于等于终点，则可以到达终点。

实现代码

class Solution {
    public boolean canJump(int[] nums) {
        int furthest=0;
        for(int i=0;i<nums.length;i++) {
            if(i<=furthest) {
                furthest=Math.max(i+nums[i],furthest);
                if(furthest>=nums.length-1)
                    return true;
            } else {
                return false;
            }
        }
        return false;
    }
}

跳跃游戏II

未完待续…