55. Jump Game


You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, orfalse otherwise.

Example 1:

Input: nums = [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: nums = [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. 

Constraints:

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 10^5

这道题说的是有一个非负整数的数组,每个数字表示在当前位置的最大跳力(这里的跳力指的是在当前位置为基础上能到达的最远位置),求判断能不能到达最后一个位置,开始博主以为是必须刚好到达最后一个位置,超过了不算,其实是理解题意有误,因为每个位置上的数字表示的是最大的跳力而不是像玩大富翁一样摇骰子摇出几一定要走几。这里可以用贪婪算法 Greedy Algorithm,因为我们只对最远能到达的位置感兴趣,所以维护一个变量 reach,表示最远能到达的位置,初始化为0。而所有小于等于 reach 的位置都可以通过连续跳跃到达的,则只要 reach 大于等于最后一位置,就说明可以跳到最后一个位置。所以问题的核心就变成了尽可能的更新 reach 为最大值,这样就可以一次遍历数组中的每个位置,若这个位置小于等于 reach,说明是在可以到达的范围内,而从该位置可以到达的最大范围就是 i + nums[i],用这个最大范围来更新 reach。若某个时刻 reach 已经大于等于 n-1 了,说明可以到达最后的位置了,不需要进一步更新了,可以直接 break 掉循环。循环退出了之后,比较 reach 和 n-1 的只,若大于等于则返回 true,否则返回 false,参见代码如下:

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size(), reach = 0;
        for (int i = 0; i < n; ++i) {
            if (i > reach || reach >= n - 1) break;
            reach = max(reach, i + nums[i]);
        }
        return reach >= n - 1;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/55

类似题目:

Jump Game II

Jump Game III

Jump Game IV

Jump Game V

Jump Game VI

Jump Game VII

Jump Game VIII

Jump Game IX

Minimum Number of Visited Cells in a Grid

Largest Element in an Array after Merge Operations

参考资料:

https://leetcode.com/problems/jump-game/

https://leetcode.com/problems/jump-game/discuss/20917/Linear-and-simple-solution-in-C++

https://leetcode.com/problems/jump-game/discuss/20923/Java-Solution-easy-to-understand

LeetCode All in One 题目讲解汇总(持续更新中…)

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,快快加入吧~)

知识星球 喜欢请点赞,疼爱请打赏❤️.

微信打赏

|

Venmo 打赏


—|—


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation