Leetcode|中等|区间贪心|55. 跳跃游戏

1 贪心算法

• 【问题转化】：跳跃覆盖范围能否覆盖终点索引？只要覆盖到了，你愿跳几步跳几步，怎么都能跳出去，因此关键问题不在于跳几步可以恰好到终点，而是能否覆盖到终点，问题一转换，一下子就好解决了！！

局部最优：每次取最大跳跃步数（取最大覆盖范围） 整体最优：最后得到整体最大覆盖范围，看是否能到终点。

代码语言：javascript复制

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if (nums.size() == 1) return true;
        // 最远覆盖的坐标
        int fastTarget = 0; 
        for (int i = 0; i <= fastTarget; i  ) {
            fastTarget = max(fastTarget, i   nums[i]);
            if (fastTarget >= nums.size() - 1) return true;
        }
        return false;
    }
};

致谢

图片来源于「代码随想录」公众号，欢迎大家关注这位大佬的公号

公众号 索引

0 人点赞