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 每次增加，直到能到达最后一个位置。