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是贪心算法的典型应用通过在每一步选择能够跳得最远的位置来最小化跳跃次数。