题目

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.

大意

每一个数字代表可以往前走几步，看能不能走到最后。

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool canJump(vector<int>& nums) 
    {
        if(nums.size()==0)
        {
            return true;
        }
        int reach =0;
        int i;
        int len =nums.size();
        for(i=0;i<len&&reach>=i;i++)
        {
            reach =max(reach,i+nums[i]);    
        }
        return i==len;
    }
};

思路

设置一个reach，代表可以走到最远的距离，遍历数组，不断更新最远的距离，同时，假如有一个序列 32104，在第四个数卡住，所以reach至少要大于遍历的序号，走到最后时，reach是3，所以走不到第四个位置，就结束循环，能走到最后就返回true，否则返回false。因为最极端的情况就是全1走完（其中有一个0都不行），所以第i个数字，他的reach至少是i。也就是走完第一个数字，至少能到第二个数字，走完第二个，至少能到第三个数字…依次类推。