Skip to main content

跳跃游戏II

· 6 min read
Eureka X
Eureka X
Mr.Nobody

力扣面试经典——45题​

💡 参考代码：​

/**
 * 计算跳跃游戏的最小跳跃次数
 * 此函数只关心最小跳跃次数，而不关心真实的跳跃路径
 * @param nums 非负整数数组，每个元素代表在该位置可以跳跃的最大长度
 * @param numsSize 数组长度
 * @return 到达最后一个下标的最小跳跃次数
 */
int jump(int* nums, int numsSize) {
    // 边界情况：数组长度小于等于1，不需要跳跃
    if (numsSize <= 1) return 0;
    
    int jumps = 0;          // 记录跳跃次数
    int currentEnd = 0;     // 当前这次跳跃能到达的最远边界，但并非真要跳到此边界
    int farthest = 0;       // 目前为止能到达的最远位置
    
    // 只需要遍历到 numsSize-2，因为题目保证能到达最后位置
    for (int i = 0; i < numsSize - 1; i++) {
        // 计算从位置i能跳到的最远位置，并更新全局最远位置
        int currentFarthest = i + nums[i];
        farthest = (farthest > currentFarthest) ? farthest : currentFarthest;
        
        // 如果到达当前跳跃的边界，必须进行下一次跳跃
        if (i == currentEnd) {
            jumps++;                // 增加跳跃次数
            currentEnd = farthest;  // 更新下一次跳跃的边界
        }
    }
    
    return jumps;  // 返回最小跳跃次数
}

📖 总结：​

点击展开题目总结

🤔 跳跃游戏 II

1️⃣ 题目核心信息​

🎯 功能描述：给定一个数组，数组中每个元素表示在该位置可以跳跃的最大长度，求到达最后一个位置的最小跳跃次数。

📥 输入输出：

  • 输入：int* nums（非负整数数组），int numsSize（数组长度）
  • 输出：到达最后一个下标的最小跳跃次数

2️⃣ 实现原理​

💡 核心思路：使用贪心算法，在每次必须跳跃时选择能跳得最远的位置，从而最小化跳跃次数。

📋 实现步骤：

  1. 维护三个变量：跳跃次数、当前跳跃边界、全局最远位置
  2. 遍历数组（除最后一个元素），不断更新能到达的最远位置
  3. 当到达当前跳跃边界时，必须进行下一次跳跃
  4. 更新跳跃次数和下一次跳跃的边界

3️⃣ 关键点解析​

🎯 代码技巧​

  • 使用贪心策略：在必须跳跃时选择最优方案
  • 双指针思想：currentEnd标记当前跳跃边界，farthest记录最远可达位置
  • 提前终止：只需遍历到倒数第二个元素

4️⃣ 使用场景​

✅ 适用情况：​

  • 求解最小跳跃次数问题
  • 数组元素表示跳跃能力的场景
  • 需要优化路径选择的问题

⚠️ 前提条件：​

  • 题目保证可以到达最后一个位置
  • 数组元素为非负整数

5️⃣ 复杂度分析​

  • ⏱️ 时间复杂度：O(n)，只需遍历一次数组
  • 💾 空间复杂度：O(1)，只使用常数额外空间

6️⃣ 注意事项​

🚩 边界情况：​

  • 数组长度为1：不需要跳跃，返回0
  • 数组长度为2：最多只需1次跳跃
  • 第一个元素为0：根据题目保证，这种情况不会出现

💥 易错点：​

  • 循环只需要到 numsSize-1，否则可能多计算一次跳跃
  • 必须在到达边界时才增加跳跃次数
  • 更新边界和最远位置的顺序不能颠倒

7⃣ 补充说明​

🎯 关键洞察​

  • jump 变量更新的位置 ≠ 实际跳跃发生的物理位置
  • jump 变量表示的是"必须做出跳跃决策"的次数

📊 算法执行逻辑​

例：nums = [2, 3, 1, 1, 4]

真实跳跃路径：0 → 1 → 4

算法计数逻辑：

  1. 位置0：确定第1次跳跃覆盖范围(0-2)
  2. 位置1,2：探索发现能跳到位置4
  3. 位置2(边界)：必须决策，jump++，确定下次跳跃范围

🎯 算法本质​

这是批量决策过程：

  • 第1次决策(jump=1)：站在起点，确定覆盖范围0-2
  • 第2次决策(jump=2)：在范围内探索，发现能到位置4

实际执行：位置0 → 位置1 → 位置4
算法计数：在必须决策时计数，非实际起跳时

💡 设计优势​

  • 提前规划：必须跳跃前已知最优选择
  • 批量处理：一次决策覆盖一个区间
  • 贪心最优：每次都选能跳最远的方案

✅ jump 变量容易误导人，它记录的是"决策次数"而非"起跳时刻"。

8⃣ 惑之未解？​

🤔 问题思考​

为什么for循环的判断条件是 i < numsSize - 1 而不是 i < numsSize？

如果使用 i < numsSize，在某些情况下（如 [2,3,1,1,4]），当能够跳转到最后位置时，jump 会多加1，导致结果错误。

🧐 深入分析​

经过再次思考，这些变量 jump、currentEnd、farthest、currentFarthest 都是根据数组下标及其对应数值来决定是否更新的。

关键理解点：

  • jump 的含义是"需要跳跃jump次才能到达数组最后一个元素"
  • 如果循环条件设定为 i < numsSize，for循环会遍历到数组的最后一个位置
  • 但当我们处理到倒数第二个位置时，已经收集了足够的信息来确定最少跳跃次数
  • 继续处理最后一个位置是不必要的，甚至可能导致错误结果

9⃣ 举一反一？😂​

最小跳跃次数 + 真实跳跃路径

/**
 * 计算跳跃游戏的最小跳跃次数和路径
 * @param nums 非负整数数组，每个元素代表在该位置可以跳跃的最大长度
 * @param numsSize 数组长度
 * @param path 用于存储跳跃路径的数组
 * @param pathSize 用于返回路径长度的指针
 * @return 到达最后一个下标的最小跳跃次数
 */
int jumpWithPath(int* nums, int numsSize, int* path, int* pathSize) {
    // 边界情况：数组长度小于等于1，不需要跳跃
    if (numsSize <= 1) {
        *pathSize = 0;
        return 0;
    }
    
    int jumps = 0;          // 记录跳跃次数
    int currentEnd = 0;     // 当前这次跳跃能到达的最远边界
    int farthest = 0;       // 目前为止能到达的最远位置
    int farthestIndex = 0;  // 能到达最远位置的索引
    
    // 记录路径
    path[0] = 0;            // 起点总是位置0
    int pathIndex = 1;
    
    // 只需要遍历到 numsSize-2，因为题目保证能到达最后位置
    for (int i = 0; i < numsSize - 1; i++) {
        // 计算从位置i能跳到的最远位置
        int currentFarthest = i + nums[i];
        
        // 更新全局最远位置和对应的索引
        if (currentFarthest > farthest) {
            farthest = currentFarthest;
            farthestIndex = i;
        }
        
        // 如果到达当前跳跃的边界，必须进行下一次跳跃
        if (i == currentEnd) {
            jumps++;                // 增加跳跃次数
            currentEnd = farthest;  // 更新下一次跳跃的边界
            path[pathIndex++] = farthestIndex;  // 记录跳跃位置
        }
    }
    
    // 添加终点
    path[pathIndex++] = numsSize - 1;
    *pathSize = pathIndex;
    
    return jumps;  // 返回最小跳跃次数
}

// 使用示例
/*
int main() {
    int nums[] = {2, 3, 1, 1, 4};
    int numsSize = 5;
    int path[100];
    int pathSize;
    
    int jumps = jumpWithPath(nums, numsSize, path, &pathSize);
    
    printf("最小跳跃次数: %d\n", jumps);
    printf("跳跃路径: ");
    for (int i = 0; i < pathSize; i++) {
        printf("%d ", path[i]);
    }
    printf("\n");
    
    return 0;
}
*/
加载评论中...