LeetCode 跳跃类问题的解题技巧：跳跃游戏与最少跳跃数
在 LeetCode 中，有一类经典的题目是关于跳跃的，例如 跳跃游戏 和 跳跃游戏 II。这些问题通常要求我们判断是否能从数组的起始位置跳跃到结束位置，或者求得最少跳跃次数。解决这类问题时，贪心算法是一个非常有效的策略。
本文将通过 跳跃游戏（Can Jump） 和 跳跃游戏 II（Jump） 两道题目，讲解如何运用贪心算法高效地解决这类问题。
1. 跳跃游戏 (Can Jump)
题目概述：
给定一个非负整数数组 nums，数组中的每个元素代表你在该位置可以跳跃的最大长度。你从数组的第一个位置开始，判断是否能够跳跃到数组的最后一个位置。
解题思路：
贪心策略：
- 目标：检查是否能够跳跃到最后一个位置。我们从数组的第一个元素开始，尝试不断跳跃，并跟踪当前能到达的最远位置。
- 核心思想：我们维护一个变量
cur，表示当前能够到达的最远位置。遍历数组时，若当前位置能够跳跃的最远位置i + nums[i]大于cur，则更新cur，如果在过程中发现当前位置无法继续跳跃（即cur不再更新），则返回False。
关键步骤：
- 从第一个位置开始，初始化
cur = 0（表示当前能跳跃到的位置）。 - 遍历每一个位置
i，如果i大于cur，则说明当前位置无法到达，返回False。 - 如果
i + nums[i]大于当前的cur，则更新cur。 - 如果遍历结束后，
cur能到达最后一个位置，则返回True。
代码实现：
class Solution:def canJump(self, nums: List[int]) -> bool:cur = 0 # 当前能到达的最远位置n = len(nums)for i in range(n):if i > cur: # 如果当前位置不能到达，返回 Falsereturn Falsecur = max(cur, i + nums[i]) # 更新当前能到达的最远位置return True # 如果遍历结束，说明能到达最后一个位置
示例：
-
输入：
nums = [2, 3, 1, 1, 4] -
输出：
True解释：可以先从下标 0 跳到下标 1，再从下标 1 跳到下标 4。
2. 跳跃游戏 II (Jump)
题目概述：
在 nums 数组中，每个元素代表你在该位置的最大跳跃长度。你需要返回从数组的起始位置到达最后一个位置所需的最少跳跃次数。
解题思路：
贪心策略：
- 目标：我们需要通过最少的跳跃次数到达数组的最后一个元素。
- 核心思想：每次跳跃时，我们选择跳得最远的点，确保每次跳跃都能覆盖尽可能多的位置。为了实现这一点，我们维护两个变量：
cur和ne。cur：表示当前跳跃到达的最远位置。ne：表示在当前跳跃中能到达的最远位置。
关键步骤：
- 初始化
cur = 0，ne = 0，res = 0，表示跳跃次数。 - 遍历数组，更新
ne为当前能跳到的最远位置。 - 每当遍历到
cur时，说明需要一次新的跳跃（即增加res），并更新cur为ne。 - 如果遍历到最后一个位置，则返回跳跃次数。
代码实现：
class Solution:def jump(self, nums: List[int]) -> int:n = len(nums)cur = 0 # 当前跳跃的最远位置ne = 0 # 当前跳跃能够达到的最远位置res = 0 # 跳跃次数for i in range(n - 1): # 不需要跳跃到最后一个位置ne = max(ne, i + nums[i]) # 更新最远跳跃位置if i == cur: # 如果当前位置已经到达了当前跳跃的最远位置res += 1 # 跳跃次数加 1cur = ne # 更新当前跳跃的最远位置if cur >= n - 1: # 如果已经能到达最后一个位置，结束breakreturn res
示例：
-
输入：
nums = [2, 3, 1, 1, 4] -
输出：
2解释：可以先从下标 0 跳到下标 1，再从下标 1 跳到下标 4。
做题技巧总结
贪心算法在跳跃问题中的应用：
-
判断能否到达最后一个位置（跳跃游戏 I）：
- 使用
cur记录当前最远可达位置，遍历时若当前位置i超过cur，说明无法到达该位置，直接返回False。 - 每次尽量更新最远可达的位置
cur，确保每一步都能够最大化覆盖区间。
- 使用
-
计算最少跳跃次数（跳跃游戏 II）：
cur和ne的配合帮助我们在每次遍历时选出最远的跳跃目标。- 每当
i == cur时，说明必须进行一次跳跃，更新cur为ne。 - 跳跃的次数
res每次增加，直到能到达最后一个位置。
贪心算法的优点：
- 时间效率高：这类问题的时间复杂度为 O(n)，适合处理大规模数据。
- 简单直观：通过维护两个变量
cur和ne，不断选择当前能跳得最远的点，快速得到最优解。
注意事项：
- 跳跃过程中要注意“死胡同”：在一些特殊情况下，可能会遇到无法跳跃的情形。例如，在跳跃游戏 II 中，如果遇到
nums[i] == 0且无法到达后续位置，就需要提前终止。 - 处理边界条件：确保在输入的边界条件下（如数组长度为 1 或所有元素都为 0）能正确处理。
总结
通过贪心算法，我们能够高效解决跳跃游戏类问题，确保以最少的跳跃次数覆盖目标区间或判断是否能到达终点。掌握这种策略，你就能在面对这类问题时游刃有余，快速找到最优解。
