力扣第 55 题 跳跃游戏

力扣第 55 题 跳跃游戏（Jump Game）。题目要求判断一个非负整数数组中，是否能够从第一个位置跳跃到最后一个位置。每个元素表示从当前位置最多可以跳跃的步数。

解题思路

我们可以用 贪心算法 来解决这个问题。贪心的核心思想是始终维护当前能够到达的最远位置，并判断是否可以覆盖到数组的最后一个位置。

1. 初始化变量 maxReach 为 0，表示当前能够跳到的最远位置。
2. 遍历数组的每个位置 i，判断：
   • 如果当前下标 i 大于 maxReach，说明无法从前面的跳跃到达位置 i，返回 false。
   • 更新 maxReach 为 max(maxReach, i + nums[i])，表示当前能够跳到的最远位置。
3. 如果遍历结束后，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];
        }
        // 如果最远位置已经可以覆盖最后一个位置，则直接返回 true
        if (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。

复杂度分析

1. 时间复杂度：$O(n)$
   • 遍历数组中的每个元素一次，线性时间复杂度。
2. 空间复杂度：$O(1)$
   • 只使用了一个变量 maxReach，空间复杂度为常数。

贪心算法的核心

贪心的本质是：

• 只关心是否能到达尽可能远的位置，而不需要模拟实际的跳跃过程。
• 一旦 maxReach 无法覆盖某个位置，直接返回 false；如果能够覆盖到最后一个位置，返回 true。