LeetCode 45. Jump Game II

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

You can assume that you can always reach the last index.
解析：
此题目是在55 Jump Game基础之上的，要求给出到达最后一个下标的最小步数。
类似预上一个题目，还是采用贪心法，用一个变量step记录最小的步数，使用last记录当前最小step下能达到的最远距离，使用reach记录step+1下能达到的最远距离。采用贪心法计算reach，reach=max(reach, i+nums[i]),当i>last时即当前遍历位置超过last覆盖范围时更新last。具体代码如下：
[cc lang=”C++”]
class Solution {
public:
int jump(vector& nums) {
int len = nums.size();
int step = 0;
int reach = 0;//定义step+1最远能到达的位置
int last = 0;//当前step所能覆盖的最远距离
for(int i=0; i< len; i++) { if(i > last )
{
step ++;
last = reach;
}
reach = max(reach, i+nums[i]);
}
return step;
}
};
[/cc]
运行结果：

参考：
http://www.cnblogs.com/lichen782/p/leetcode_Jump_Game_II.html