[数据结构与算法]力扣：55. 跳跃游戏

·1、简单做法

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int thesize=nums.size();
        int max=0;
        bool* can=new bool[thesize];
        memset(can,0,thesize*sizeof(bool));
        can[0]=1;
         for(int i=0;i<thesize;++i)
         {
            if(!can[i]) return false;
            if(i+nums[i]>max) 
            {
                if(i+nums[i]>=thesize-1) return true;
                for(int j=i+1;j<=i+nums[i];++j) can[j]=true;
                max=i+nums[i];
            }
         }
         return true;
    }
};

?2、优化一下

用一个max去记录所能到达的最远下标

遍历数组，如果i（即当前下标）大于max，那说明通过前面的跳跃无法到达这里。

i+nums[i]表示在这个下标能跳到的最远距离，如果大于max，那就说明能跳的更远，所以更新max。

优化一下，如果所能跳到的最远下标大于等于最后下标，则可以直接返回true。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int thesize=nums.size();
        int max=0;
         for(int i=0;i<thesize;++i)
         {
            if(i>max) return false;
            if(i+nums[i]>max)  max=i+nums[i];
            if(max>=thesize-1) return true;
         }
         return true;
    }
};