[数据结构与算法]leetcode 55.跳跃游戏 贪心

题目描述

leetcode 55.跳跃游戏

思路

其实本题的核心是不要关心跳几步，关键在于以当前为起点可跳的覆盖范围。因此问题转化为跳跃覆盖范围可不可以覆盖到终点，每次取最大跳跃步数（取最大覆盖范围），最后看最大覆盖范围，看是否能到终点，可以用贪心的方法解决这个问题。

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

题意转化：以位置 $i$ 为起点，它能跳跃到的最大下标为 $i+nums[i]$ ，在往右移动的过程中，不断维护能跳跃到的最大下标$cover$，这个值大于等于 最后一个位置的下标$nums.size()?1$，即 $cover\ge nums.size()?1$，那么最后一个位置可以到达。

遍历 数组 让 $i$ 每移动一个元素，$cover$得到该位置新的覆盖范围：
计算最大覆盖范围 cover=max(cover,i+nums[i]);
若 cover>=nums.size()-1，直接 return true 。

代码

如果一个位置能够到达，那么这个位置左侧所有位置都能到达。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if(nums.size()==1) return true; //如果数组就一个位置，那起始位置就是目的位置，直接返回true
        int cover=-1; //能覆盖到的最大范围
        for(int i=0;i<nums.size();i++)
        { //遍历数组的每一个位置
            cover=max(cover,i+nums[i]);  //更新最大范围
            if(cover==i&&cover!=nums.size()-1) //如果更新完了发现当前的最大范围，就是我们遍历到这个位置，说明在这个位置的左边及其这个位置本身，怎么跳，都会跳到这个位置，且不能再往右跳下去了，到头了
//但是这个位置也不能是最后一个位置，不然还是能到达的
                return false;
            if(cover>=nums.size()-1)  //最大范围覆盖到了终点，说明能到达
                return true;   //返回true
        }
        return false;
    }
};

更新完最大范围cover以后，表明当前位置以及其左边的所有位置，向右跳跃，所能到达的最远处就是cover了。
所以当cover==i&&cover!=nums.size()-1时，一定是在终点之前停下了，且不能再往右跳。