LeetCode 第 45 题“跳跃游戏 II”

好的，我来帮你解释一下 LeetCode 第 45 题“跳跃游戏 II”，这是一道经典的贪心算法题目。

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

举个例子：
假设输入数组是 [2,3,1,1,4]，你可以这样跳跃：

1. 从位置 0 跳到位置 1（跳了 1 步）。
2. 从位置 1 跳到位置 4（跳了 1 步）。
   所以最少需要 2 次 跳跃。

解题思路：
这个问题可以用贪心算法来解决。贪心算法的核心思想是在每一步都选择最优的决策，从而达到全局最优解。

1. 定义变量：

   • end：当前能跳到的最远位置。
   • farthest：在当前跳跃范围内，能跳到的最远位置。
   • jumps：记录跳跃的次数。

2. 遍历数组：

   • 从第一个位置开始，遍历数组。
   • 对于每个位置，计算从这个位置能跳到的最远位置（i + nums[i]），并更新 farthest。
   • 当遍历到当前能跳到的最远位置（end）时，更新 end 为 farthest，并增加跳跃次数（jumps++）。

3. 结束条件：

   • 当 end 超过或等于数组的最后一个位置时，停止遍历。

具体步骤：

1. 初始化 end = 0，farthest = 0，jumps = 0。
2. 遍历数组：
   • 对于每个位置 i，更新 farthest = max(farthest, i + nums[i])。
   • 如果 i == end，说明当前跳跃范围已经用完，需要进行下一次跳跃：
     • 更新 end = farthest。
     • 增加跳跃次数 jumps++。
3. 当 end 超过或等于数组的最后一个位置时，返回 jumps。

代码示例（Python）：

def jump(nums):n = len(nums)end = 0farthest = 0jumps = 0for i in range(n - 1):  # 不需要遍历最后一个位置farthest = max(farthest, i + nums[i])if i == end:  # 当前跳跃范围用完jumps += 1end = farthestif end >= n - 1:  # 如果已经可以到达或超过最后一个位置breakreturn jumps

关键点：

• 贪心策略：每次选择当前范围内能跳到的最远位置，这样可以保证用最少的跳跃次数。
• 边界条件：注意数组的边界，避免越界。

希望这个解释对你有帮助！如果你还有其他问题，随时问我哦。