力扣第45题“跳跃游戏 II”

力扣第45题“跳跃游戏 II”

题目描述

给定一个非负整数数组 nums，其中每个元素代表你在该位置可以跳跃的最大长度。目标是从数组的第一个位置开始跳跃，跳到最后一个位置，用最少的跳跃次数完成这一目标。

示例

输入: nums = [2,3,1,1,4]
输出: 2
解释: 从索引 0 跳到索引 1，然后跳到最后一个位置。

解题思路

1. 贪心策略：在每一步跳跃时，我们选择跳到当前可到达范围内的最远位置。
2. 逐步推进：遍历数组时，维护当前可以到达的范围，若遍历到边界，更新步数并扩展新的边界范围，直到抵达终点。
3. 提前结束：若当前范围已经可以覆盖到终点位置，则可以直接返回跳跃次数。

代码实现

下面是代码的详细实现以及逐行注释说明。

#include <stdio.h>

// 跳跃游戏 II 主函数
int jump(int* nums, int numsSize) {
    if (numsSize <= 1) return 0;  // 当数组长度为1时，不需要跳跃

    int jumps = 0;           // 跳跃次数
    int currentEnd = 0;      // 当前跳跃的边界
    int farthest = 0;        // 当前能跳到的最远位置

    for (int i = 0; i < numsSize - 1; i++) {
        farthest = (i + nums[i] > farthest) ? i + nums[i] : farthest;  // 更新最远距离

        // 当达到当前边界时，必须进行跳跃，更新边界
        if (i == currentEnd) {
            jumps++;
            currentEnd = farthest;

            // 如果当前边界已经能到达终点，则跳出循环
            if (currentEnd >= numsSize - 1) {
                break;
            }
        }
    }
    return jumps;
}

// 测试代码
int main() {
    int nums[] = {2, 3, 1, 1, 4};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    
    int result = jump(nums, numsSize);
    printf("最少跳跃次数为: %d\n", result);
    
    return 0;
}

代码解析

1. 初始化变量：

   int jumps = 0;           // 跳跃次数
   int currentEnd = 0;      // 当前跳跃的边界
   int farthest = 0;        // 当前能跳到的最远位置
   

   • jumps 记录跳跃次数。
   • currentEnd 表示当前跳跃的边界位置。
   • farthest 表示在当前步数内，能跳到的最远位置。

2. 遍历数组，计算跳跃次数：

   for (int i = 0; i < numsSize - 1; i++) {
       farthest = (i + nums[i] > farthest) ? i + nums[i] : farthest;
       ...
   }
   

   • 遍历每个位置，将能跳到的最远位置不断更新。

3. 在达到边界时更新跳跃次数：

   if (i == currentEnd) {
       jumps++;
       currentEnd = farthest;
       if (currentEnd >= numsSize - 1) {
           break;
       }
   }
   

   • 当 i 达到 currentEnd 时，表示需要跳跃到下一步，更新跳跃次数和新的边界。
   • 若 currentEnd 已经可以达到或超过数组的末尾，则终止循环。

4. 返回结果：

   • 最后返回 jumps，即为从起点跳到终点所需的最小跳跃次数。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。遍历一遍数组即可得到结果。
• 空间复杂度：O(1)，只需常量空间来存储变量。