LeetCode:跳跃游戏

55. 跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例 2:
输入:* [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

思路：

方法一：
维护一个最右能到达的距离rightmost，然后从0开始依次遍历数组，对于第i个位置，它能到达的最右位置为i+nums[i]，与维护的rightmost比较，如果大于rightmost则更新rightmost，如果rightmost已经大于等于nums.size()-1，那么则成功。因为i时递增的，如果发现rightmost小于i了，说明不可到达，此时返回false。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int rightmost=0;
        for(int i=0;i<nums.size();++i)
        {
            if(i>rightmost)  //存在到达不了的位置
                return false;
            rightmost=max(rightmost,i+nums[i]); //更新rightmost
            if(rightmost>=nums.size()-1)  //提前结束，之后的元素就不用遍历了
                return true;
        }
        return true;
    }
};

方法二：
发现只有数组中存在0的时候，才有可能无法到达最后一个元素。如果全不是0，则肯定可以到达最后元素。于是可以对0出现的位置做分类讨论。
如果nums[0]=0，则说明不能跳跃，此时数组只有0一个元素则成功，否则失败。
对于一般情况，比如num[i]=0，那么只要在i之前存在一个元素j，使得num[j]>i-j即可跳过该0。
如果最后一个元素为0，若存在j，使得num[j]>=nums.size()-1 - j即可跳跃成功，取等于也可以的原因是到达最后一个位置就不需要再跳了。如果一般情况取等于号则不可以，因为还需要再跳，但是不能跳了。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if (nums[0]==0)  
        {
            if (nums.size()==1) 
                return true;
            else 
                return false;
        }
        bool flag=1; //标记nums[i]=0时是否成功跳过
        for(int i=0;i<nums.size();++i)
        {
            if(nums[i]==0){
                flag=0;  //nums[i]=0，触发条件flag=0
                for(int j=i-1;j>=0;--j)
                {
                    if((i!=nums.size()-1&&nums[j]>i-j)||(i==nums.size()-1&&nums[j]>=(i-j)))
                    {
                        flag=1; //如果flag=1，说明nums[i]可以由i之前的元素跳过去
                        break; //跳出当前循环，即j元素已经能满足，不需要再往前找了。
                    }
    
                }
                if(!flag) //此时flag为0，说明nums[i]不能由i之前的元素顺利跳过，直接返回false
                    return false;
            }
        }
        return flag;
    }
};

自己果然是个经验宝宝。。。。
那就多看看题解，加油吧。。。