忍者算法

Appearance

跳跃游戏II：探索最少跳跃次数的智慧之路！ ​

大家好，我是忍者算法。今天让我们继续深入探讨跳跃游戏的进阶版本。在第一个版本中，我们只需要判断能否到达终点，而这次我们要找出到达终点的最少跳跃次数。这个问题看似简单，但其中蕴含着更深层的思考。让我们一起揭开它的神秘面纱！

📚 从生活场景理解 ​

想象你在玩一个跳石头过河的游戏。河面上有一系列石头，每块石头上都标着一个数字，表示你站在这块石头上最远能跳多远。你想用最少的跳跃次数到达对岸。这就像在规划旅程，每一步都要考虑如何让整体路径最优。

💡 问题的精髓 ​

给定一个非负整数数组nums，你最初位于数组的第一个位置，数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。题目假设你总是可以到达数组的最后一个位置。

举个例子：

java
输入：nums = [2,3,1,1,4]
输出：2
解释：跳到最后一个位置的最小跳跃数是 2：
     跳 1 步，从下标 0 到 1
     跳 1 步，从下标 1 到 4
java
class Solution {
    public int jump(int[] nums) {
        // 如果数组长度为1，已经在终点，不需要跳跃
        if (nums.length <= 1) return 0;
        
        // 记录跳跃次数
        int jumps = 0;
        // 当前这一跳能够到达的最远位置
        int currentMaxReach = 0;
        // 下一跳能够到达的最远位置
        int nextMaxReach = 0;
        
        // 遍历数组，注意这里只需要遍历到倒数第二个位置
        // 因为一旦能够到达最后一个位置，就不需要再跳了
        for (int i = 0; i < nums.length - 1; i++) {
            // 更新在遍历过程中能够到达的最远位置
            nextMaxReach = Math.max(nextMaxReach, i + nums[i]);
            
            // 如果到达当前跳跃能到达的最远位置
            // 说明需要进行下一跳了
            if (i == currentMaxReach) {
                // 更新当前能够到达的最远位置
                currentMaxReach = nextMaxReach;
                // 跳跃次数加1
                jumps++;
                
                // 如果已经能够到达最后一个位置，就可以结束了
                if (currentMaxReach >= nums.length - 1) {
                    break;
                }
            }
        }
        
        return jumps;
    }
    
    // 另一种实现方式：区间贪心
    public int jumpAlternative(int[] nums) {
        int n = nums.length;
        // 记录跳跃次数
        int jumps = 0;
        // 当前跳跃覆盖的区间：[left, right]
        int left = 0;
        int right = 0;
        
        // 当右边界没有达到最后一个位置时
        while (right < n - 1) {
            // 找出从当前区间内能够到达的最远位置
            int farthest = 0;
            for (int i = left; i <= right; i++) {
                farthest = Math.max(farthest, i + nums[i]);
            }
            
            // 更新下一个区间的边界
            left = right + 1;
            right = farthest;
            
            // 完成一次跳跃
            jumps++;
        }
        
        return jumps;
    }
}

📝 深入理解解题思路 ​

这道题的美妙之处在于它的贪心策略。让我们通过一个形象的比喻来理解：

想象你在玩"跳格子"游戏，但每次跳跃时你都要思考两件事：

  1. 这一跳能直接到达的范围（currentMaxReach）
  2. 在这个范围内起跳，下一跳最远能到哪里（nextMaxReach）

🎨 让我们用图来理解这个过程 ​

svg
<svg viewBox="0 0 800 500" xmlns="http://www.w3.org/2000/svg">
  <!-- 背景 -->
  <rect width="800" height="500" fill="#f8f9fa"/>
  
  <!-- 标题 -->
  <text x="400" y="40" text-anchor="middle" font-size="20" fill="#1976d2">跳跃游戏II：贪心策略可视化</text>
  
  <!-- 数字格子 -->
  <g transform="translate(100,100)">
    <!-- 第一跳可达范围 -->
    <rect x="0" y="0" width="200" height="100" fill="#2196f3" opacity="0.2"/>
    <text x="100" y="130" text-anchor="middle" font-size="14">第一跳可达范围</text>
    
    <!-- 第二跳可达范围 -->
    <rect x="200" y="0" width="400" height="100" fill="#4caf50" opacity="0.2"/>
    <text x="400" y="130" text-anchor="middle" font-size="14">第二跳可达范围</text>
    
    <!-- 数字格子 -->
    <g>
      <rect x="0" y="20" width="80" height="60" fill="white" stroke="#1976d2"/>
      <text x="40" y="55" text-anchor="middle" font-size="24">2</text>
    </g>
    <g>
      <rect x="100" y="20" width="80" height="60" fill="white" stroke="#1976d2"/>
      <text x="140" y="55" text-anchor="middle" font-size="24">3</text>
    </g>
    <g>
      <rect x="200" y="20" width="80" height="60" fill="white" stroke="#1976d2"/>
      <text x="240" y="55" text-anchor="middle" font-size="24">1</text>
    </g>
    <g>
      <rect x="300" y="20" width="80" height="60" fill="white" stroke="#1976d2"/>
      <text x="340" y="55" text-anchor="middle" font-size="24">1</text>
    </g>
    <g>
      <rect x="400" y="20" width="80" height="60" fill="white" stroke="#1976d2"/>
      <text x="440" y="55" text-anchor="middle" font-size="24">4</text>
    </g>
    
    <!-- 跳跃路径 -->
    <path d="M 40 50 Q 140 0 240 50" fill="none" stroke="#f44336" stroke-width="2"/>
    <path d="M 240 50 Q 340 0 440 50" fill="none" stroke="#f44336" stroke-width="2"/>
  </g>
  
  <!-- 说明文字 -->
  <g transform="translate(100,300)">
    <text x="0" y="0" font-size="16" fill="#1976d2">贪心策略说明：</text>
    <text x="0" y="30" font-size="14">1. 第一跳：从位置0跳到位置2（可达范围[1,2]中选择最优）</text>
    <text x="0" y="60" font-size="14">2. 第二跳：从位置2跳到位置4（可达范围[3,4]中选择最优）</text>
    <text x="0" y="90" font-size="14">总跳跃次数：2次</text>
  </g>
</svg>

🎯 关键思考点 ​

让我们深入理解这个解法的几个关键点：

  1. 为什么需要维护两个边界？ 这是这个解法的精髓。currentMaxReach告诉我们当前这一跳能到哪里，而nextMaxReach则在探索下一跳的可能性。这就像是在探索地图时，既要知道当前位置，又要看看远处的风景。

  2. 贪心策略的正确性 在每个可达区间内，我们都选择能跳得最远的位置作为下一跳的目标。这个策略之所以是最优的，是因为：如果存在一个跳得更少的方案，那么它一定也能被我们的贪心策略覆盖到。

  3. 边界条件的处理 注意我们的遍历只需要到达倒数第二个位置，因为一旦能够到达最后一个位置，就不需要再跳了。这是一个重要的优化。

🌟 代码的优化思路 ​

  1. 空间优化 我们只需要几个变量就可以完成整个算法，空间复杂度为O(1)。

  2. 时间优化 通过维护两个边界，我们避免了重复计算，时间复杂度为O(n)。

  3. 提前结束 一旦发现当前可达范围已经覆盖了终点，就可以立即结束遍历。

💡 举一反三 ​

这种贪心策略还可以应用在其他类似的问题上：

  1. 带体力值的跳跃游戏
java
// 每次跳跃消耗体力值，求到达终点的最小体力值消耗
public int minEnergyJump(int[] nums, int[] energy) {
    // 类似的思路，但需要考虑体力值的消耗
}
  1. 带障碍物的跳跃游戏
java
// 某些位置有障碍物不能跳到，求最少跳跃次数
public int jumpWithObstacles(int[] nums, boolean[] obstacles) {
    // 需要在更新nextMaxReach时考虑障碍物
}

🎓 题目带来的启示 ​

这道题目给我们的启示是：

  1. 有时候，看似需要动态规划的问题，用贪心策略可能会有更优雅的解法。

  2. 在解决问题时，维护多个状态（这里是两个边界）可能会让问题变得更清晰。

  3. 优化代码时，要注意观察是否存在可以提前结束的条件。

作者：忍者算法 公众号：忍者算法 🎁 回复【刷题清单】获取LeetCode高频面试题合集 🧑‍💻 回复【代码】获取多语言完整题解 💡 回复【加群】加入算法交流群，一起进步 #算法面试 #LeetCode #贪心算法 #动态规划

这道题不仅教会我们一个解决特定问题的方法，更重要的是展示了如何通过维护多个状态来简化问题的复杂度。如果你对这个话题还有任何疑问，欢迎在评论区讨论！