巩义网站优化,免费做游戏网站,汕头公关公司,山西手动网站建设推荐平台题目
55. 跳跃游戏
中等
相关标签
贪心 数组 动态规划
给你一个非负整数数组 nums #xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标#xff0c;如果可以#xff0c;返回 true 你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标如果可以返回 true 否则返回 false 。 示例 1
输入nums [2,3,1,1,4]
输出true
解释可以先跳 1 步从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。示例 2
输入nums [3,2,1,0,4]
输出false
解释无论怎样总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 所以永远不可能到达最后一个下标。提示
1 nums.length 1040 nums[i] 105
思路和解题方法 首先我们维护一个变量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(vectorint 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(vectorint nums) {int n nums.size();vectorbool canReach(n, false); // 创建一个长度为n的数组初始值都为falsecanReach[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]; // 返回最后一个位置是否可达}
};觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
