55. 跳跃游戏-Toy模板网

这篇具有很好参考价值的文章主要介绍了55. 跳跃游戏。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目介绍

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：文章来源地址https://www.toymoban.com/news/detail-611249.html

1 <= nums.length <= 3 * 104
0 <= nums[i] <= 105

解答

C++

class Solution {
public:
    // 把nums上的数字当做能量
    // 假设每往前走一格需要消耗一格能量
    bool canJump(vector<int>& nums) {
        if(nums.size() == 0) return true;

        int cur = nums[0], i = 1; // i 表示走的位置
        for(; cur != 0 && i < nums.size(); ++i)
        {
            cur--;
            // 遇到能量多余当前剩余能量的位置时，替换为当前位置的能量值
            if(cur < nums[i]) cur = nums[i];
        }
        return i == nums.size();
    }

    // 每个位置都计算自己能达到的最远距离
    // 算出来能达到的最远距离是最后一个位置说明可达
    bool canJump1(vector<int>& nums) {
        int maxDis = 0;
        if(nums.size() == 0)    return true;

        // 迭代进行计算，前面计算出的最远可达距离
        // 来判断是否能从某点出发
        for(int i = 0; i < nums.size(); ++i)
        {
            // 无法到达位置i，直接return
            if(i > maxDis)
            {
                return false;
            }
            maxDis = max(maxDis, i + nums[i]);
        }
        return true;
    }
};

python

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        maxDis = 0
        if len(nums) == 0:
            return True

        for i in range(0, len(nums)):
            if(i > maxDis):
                return False
            maxDis = max(maxDis, i + nums[i])

        return True