从零开始的LeetCode刷题日记：55. 跳跃游戏
一.相关链接
题目链接：55. 跳跃游戏
二.心得体会
这一道贪心算法的题目的核心其实是要知道每一个点可以跳到哪些位置。最好想到的一个贪心思路是每次都跳最大的，但也很容易找到反例。
这道题的核心是一个概念：覆盖范围！覆盖范围指的是当前遍历过的子序列所能让我们到达的最远位置。比如第一个节点是2，那么我们的覆盖范围就是3个节点（包括第一个节点本身）。
那么每次就在覆盖范围里面进行往后遍历，并不断更新我们的最大覆盖范围。如果最后覆盖了最后一个节点，说明能达到终点，反之达不到。
三.代码
class Solution {
public:
bool canJump(vector<int>& nums) {
if(nums.size()==1) return true;
int jumpStep = 0;
int curStep = 0;
for(int i=0;i<=jumpStep;i++) {
curStep = i + nums[i]; //计算当前节点的覆盖范围
if(curStep > jumpStep) jumpStep = curStep; //判断是否为新的最大覆盖区间
if(jumpStep >= nums.size()-1) return true; //覆盖了最后一个节点就说明可达
}
return false;
}
};