网站默认图,wordpress视频分享,河南新冠防控,唐山网站建设外包公司哪家好力扣第 55 题 跳跃游戏#xff08;Jump Game#xff09;。题目要求判断一个非负整数数组中#xff0c;是否能够从第一个位置跳跃到最后一个位置。每个元素表示从当前位置最多可以跳跃的步数。
解题思路
我们可以用 贪心算法 来解决这个问题。贪心的核心思想是始终维护当前…力扣第 55 题 跳跃游戏Jump Game。题目要求判断一个非负整数数组中是否能够从第一个位置跳跃到最后一个位置。每个元素表示从当前位置最多可以跳跃的步数。
解题思路
我们可以用 贪心算法 来解决这个问题。贪心的核心思想是始终维护当前能够到达的最远位置并判断是否可以覆盖到数组的最后一个位置。
初始化变量 maxReach 为 0表示当前能够跳到的最远位置。遍历数组的每个位置 i判断 如果当前下标 i 大于 maxReach说明无法从前面的跳跃到达位置 i返回 false。更新 maxReach 为 max(maxReach, i nums[i])表示当前能够跳到的最远位置。 如果遍历结束后maxReach 大于等于数组的最后一个下标则返回 true。 C语言实现
#include stdio.h
#include stdbool.h// 跳跃游戏判断函数
bool canJump(int* nums, int numsSize) {int maxReach 0; // 能到达的最远位置for (int i 0; i numsSize; i) {// 如果当前位置超过能到达的最远位置说明无法继续跳跃if (i maxReach) {return false;}// 更新能到达的最远位置if (i nums[i] maxReach) {maxReach i nums[i];}// 如果最远位置已经可以覆盖最后一个位置则直接返回 trueif (maxReach numsSize - 1) {return true;}}return false;
}int main() {int nums[] {2, 3, 1, 1, 4};int numsSize sizeof(nums) / sizeof(nums[0]);if (canJump(nums, numsSize)) {printf(可以跳到最后一个位置\n);} else {printf(无法跳到最后一个位置\n);}return 0;
}示例解析
示例 1:
输入
int nums[] {2, 3, 1, 1, 4};输出
可以跳到最后一个位置解释
从第一个位置跳跃 2 步到索引 1接着跳跃 3 步到最后一个位置。
示例 2:
输入
int nums[] {3, 2, 1, 0, 4};输出
无法跳到最后一个位置解释
无论怎么跳跃都无法跳过索引 3 的位置因为索引 3 的值为 0。 复杂度分析
时间复杂度 O ( n ) O(n) O(n) 遍历数组中的每个元素一次线性时间复杂度。 空间复杂度 O ( 1 ) O(1) O(1) 只使用了一个变量 maxReach空间复杂度为常数。 贪心算法的核心
贪心的本质是
只关心是否能到达尽可能远的位置而不需要模拟实际的跳跃过程。一旦 maxReach 无法覆盖某个位置直接返回 false如果能够覆盖到最后一个位置返回 true。
