LeetCode 55. Jump Game

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.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.
解析：
给定一组非负的整数，初始位置在数组中的第一个位置，数组中的每一个元素代表所能跳的最大步数，确定能否到达数组最后一个元素，即使超了也算。
此题目采用贪心算法Greedy Algorithm，因为只希望知道能否到达末尾，也就是说我们只对最远能到达的位置感兴趣，所以我们维护一个变量reach，表示最远能到达的位置，初始化为0。遍历数组中每一个数字，如果当前坐标大于reach或者reach已经抵达最后一个位置则跳出循环，否则就更新reach的值为其和i + nums[i]中的较大值，其中i + nums[i]表示当前位置能到达的最大位置。其中当前坐标大于reach表示当前遍历的位置即便是最远达到距离也没有达到，所以提取终止循环。
代码如下：
[cc lang=”C++”]
class Solution {
public:
bool canJump(vector& nums) {
int len = nums.size();
int reach = 0;//定义最远能到达的位置
for(int i=0; i< len; i++) { if(i > reach || reach >= len -1)//i>reach表示当前遍历的位置reach已经无法到达，
//reach>=len-1表示reach已经可以到达末尾了
break;
reach = max(reach, i+nums[i]);
}
return reach >= len -1;
}
};
[/cc]

参考：https://www.cnblogs.com/grandyang/p/4371526.html