力扣第55题跳跃游戏 c++ 贪心 + 覆盖加暴力超时参考-Toy模板网

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

题目

55. 跳跃游戏

中等

思路和解题方法

首先，我们维护一个变量cover，表示当前能够覆盖的最远距离。如果数组只有一个元素，则一定可以到达终点，直接返回true。

然后，我们从位置0开始遍历数组，遍历范围是当前可覆盖范围内的所有位置，包括位置i。在遍历过程中，不断更新cover，使其取最大值。

如果在遍历过程中发现cover已经覆盖了数组的最后一个位置（即cover >= nums.size() - 1），则说明可以到达终点，直接返回true。

如果最终没有到达终点，则说明无法到达，返回false。

复杂度

时间复杂度:

O(n)

时间复杂度是O(n)，其中n是输入数组的长度。这是因为我们只需要一次遍历数组即可完成判断。

空间复杂度

O(1)

空间复杂度是O(1)，即常数级别的额外空间。除了几个变量（cover、i）以及函数返回值外，代码并没有使用额外的数组或数据结构来存储中间结果。因此，空间复杂度是常数级别的。

c++ 代码

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover = 0;  // 当前能够覆盖的最远距离
        if (nums.size() == 1) return true; // 如果只有一个元素，则一定可以到达
        for (int i = 0; i <= cover; i++) { // 遍历当前可覆盖范围内的所有位置
                                           // 注意这里的等于号，因为 i 指的是当前位置，所以必须要考虑到 i 也可以到达
            cover = max(i + nums[i], cover); // 更新能够覆盖的最远距离
                                             // 这里的 max 函数是为了保证更新后的 cover 是最大的
            if (cover >= nums.size() - 1) return true; // 如果当前能够覆盖的最远距离已经覆盖了终点，则说明可以到达终点
        }
        return false; // 如果最后还没有到达终点，则说明无法到达
    }
};

本人试过了O(n*n)的代码，超出时间限制了

具体暴力的代码（c++)

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        vector<bool> canReach(n, false); // 创建一个长度为n的数组，初始值都为false
        canReach[0] = true; // 初始位置可达
        
        for (int i = 0; i < n; i++) {
            if (!canReach[i]) continue; // 如果当前位置不可达，则跳过
            
            int maxJump = min(i + nums[i], n - 1); // 当前位置最远能跳到的位置
            for (int j = i + 1; j <= maxJump; j++) {
                canReach[j] = true; // 将可达位置标记为true
            }
        }
        
        return canReach[n - 1]; // 返回最后一个位置是否可达
    }
};

力扣第55题跳跃游戏 c++ 贪心 + 覆盖加暴力超时参考,leetcode,贪心,数据结构,leetcode,c++,算法,贪心,覆盖