LeetCode 跳跃游戏II题解

LeetCode 跳跃游戏II题解

题目描述

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

示例：

输入：nums = [2,3,1,1,4]
输出：2

解题思路

方法：贪心

思路：

• 使用贪心算法，在每一步都选择能够跳得最远的位置。
• 维护当前覆盖范围和下一步能够跳得最远的范围。
• 当当前位置达到当前覆盖范围的边界时，增加跳跃次数并更新覆盖范围。

复杂度分析：

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

代码实现

def jump(nums): jumps = 0 cur_end = 0 farthest = 0 for i in range(len(nums) - 1): farthest = max(farthest, i + nums[i]) if i == cur_end: jumps += 1 cur_end = farthest return jumps # 测试 def test_jump(): nums = [2, 3, 1, 1, 4] print(jump(nums)) # 输出：2 if __name__ == "__main__": test_jump()

总结

跳跃游戏II是贪心算法的典型应用，通过在每一步选择能够跳得最远的位置来最小化跳跃次数。