55 Jump Game (Medium)

主要有两种思路：
一、
本题只需要判断能否到达最后一个数，那么可以采用贪心策略，到达某个位置i后，在直接在这个位置的基础上走nums[i]步，主要保证能一直前进，就能达到终点；
那么，什么时候才不能一直前进呢？
答案是，遇到0的时候，遇到nums[i]=0的时候，只要我们想办法跳过这个0，那么就可以确保我们可以继续前进。
所以遇到0时的处理方法是，往回搜索，设当前的位置为pos，即nums[pos]=0，一直搜索之前的数，判断nums[i]+i是否大于nums[pos]，大于则可以继续上述的贪心算法，假如一直跳不过0（即搜索到i=0仍跳不过pos），则return false。

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

代码如下：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if(nums.size()==1) return true;
        int pos=0;
        while(pos<nums.size()-1)         {             if(nums[pos]!=0)             {//走最远的位置                 pos=nums[pos]+pos;             }             else             {//如果最远的位置为0                 int now=pos;                 for(int i=pos;i>=0;i--)
                {//找到能跳过0的位置
                    if(i+nums[i]>now) 
                    {
                        pos=i+nums[i];
                        break;
                    }
                }
                if(pos==now) 
                {//找不到跳过0，则false
                    return false;
                }
            }
        }
        return true;
    }
};