algorithms►leetcode

012-跳跃游戏能否到终点+最小跳跃次数（贪心算法）

跳跃游戏问题（图文解析）

跳跃游戏 I（能否到达终点）

问题描述

给定一个非负整数数组 nums，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。

示例

输入：nums = [2,3,1,1,4]
输出：true
解释：从位置 0 跳到位置 1，再从位置 1 跳到位置 4。

解题思路：贪心算法

  1. 维护一个变量 maxReach 表示当前能到达的最远位置
  2. 遍历数组，更新 maxReach
  3. 如果当前位置超过了 maxReach，说明无法继续前进
  4. 如果 maxReach 能覆盖最后一个位置，返回 true

JavaScript实现

1
2
3
4
5
6
7
8
9
10
function canJump(nums) {
    //maxReach表示能到达的最大索引位置
    let maxReach = 0;
    for (let i = 0; i < nums.length; i++) {
        if (i > maxReach) return false;
        maxReach = Math.max(maxReach, i + nums[i]);
        if (maxReach >= nums.length - 1) return true;
    }
    return true;
}

图示说明（nums = [2,3,1,1,4]）

位置: 0(2) → 1(3) → 2(1) → 3(1) → 4(4)
步骤:
1. i=0: maxReach = max(0, 0+2) = 2
   [可以覆盖位置1,2]
   
2. i=1: 1 <= 2 (可以到达)
   maxReach = max(2, 1+3) = 4
   [可以覆盖位置4，直接返回true]

跳跃游戏 II（最少跳跃次数）

问题描述

在保证能到达终点的前提下，找出最少的跳跃次数。

示例

输入：nums = [2,3,1,1,4]
输出：2
解释：最少需要跳2次：0 → 1 → 4。

解题思路：贪心算法优化

  1. 维护三个变量：

    • maxReach：当前能到达的最远位置
    • steps：当前步数能到达的边界
    • jumps：跳跃次数

  2. 遍历数组：

    • 更新 maxReach
    • 到达边界时增加跳跃次数，并更新边界

JavaScript实现

1
2
3
4
5
6
7
8
9
10
11
function jump(nums) {
    let jumps = 0, maxReach = 0, steps = 0;
    for (let i = 0; i < nums.length - 1; i++) {
        maxReach = Math.max(maxReach, i + nums[i]);
        if (i === steps) {
            jumps++;
            steps = maxReach;
        }
    }
    return jumps;
}

图示说明（nums = [2,3,1,1,4]）

位置: 0(2) → 1(3) → 2(1) → 3(1) → 4(4)
步骤:
1. i=0:
   - maxReach = max(0, 0+2) = 2
   - steps=0 (到达边界)
   - jumps=1, steps更新为2
   [第1跳可以到达位置1,2]

2. i=1:
   - maxReach = max(2, 1+3) = 4
   - i ≠ steps (1≠2)
   
3. i=2:
   - maxReach保持4
   - i=steps=2 (到达边界)
   - jumps=2, steps更新为4
   [第2跳可以到达位置4]
   
4. 结束，总共跳了2次

关键点总结

  1. 贪心选择：每次选择能跳得最远的位置

  2. 跳跃游戏I：

    • 时间复杂度：O(n)
    • 空间复杂度：O(1)
    • 只需判断能否到达终点

  3. 跳跃游戏II：

    • 时间复杂度：O(n)
    • 空间复杂度：O(1)
    • 需要计算最少跳跃次数
    • 注意遍历到 nums.length - 1 即可

  4. 边界情况：

    • 空数组或单元素数组
    • 包含0的情况（如 [3,2,1,0,4]）

常见误区

  1. 认为必须按最大步数跳跃（实际上可以跳1~最大步数的任意值）
  2. 在跳跃游戏II中使用BFS导致效率低下
  3. 忽略数组包含0的情况处理

复杂度对比

算法 时间复杂度 空间复杂度
动态规划 O(n²) O(n)
贪心算法 O(n) O(1)

贪心算法是这类问题的最优解。