跳跃游戏

题目

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

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

判断你是否能够到达最后一个位置。

具体思路

设置一个cover，每次记录当前可以跳跃到的最大位置

再在循环中不断改变，更新cover

一旦cover能覆盖到 数组最后端 那么就可以完成跳跃；

关键点在于：跳到当前的位置之后，之前已有的记录是无效的

具体代码

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover = nums[0];
        if (nums.size() <= 1)
            return true;
        // 这里是可以等于cover的看示例[1,2]:如果cover刚好是1，第一个for循环会被跳过
        for (int i = 1; i <= cover; i++) {
            cover = max(cover, nums[i] + i);
            // 要跳到当前的数组最后一位，是nums.size() - 1
            if (cover >= nums.size() - 1)
                return true;
        }
        return false;
    }
};

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