【LeetCode刷题】跳跃游戏

给你一个非负整数数组nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回true；否则，返回false。

示例 1：

输入：nums = [2,3,1,1,4]输出：true解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]输出：false解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

• 1 <= nums.length <=
• 0 <= nums[i] <=

解题思路：

本题采用贪心算法，通过维护【当前能到达的最远下标】来判断是否能到达终点，时间复杂度为 O (n)（仅遍历数组一次），空间复杂度为 O (1)（仅用常数额外空间）：

1. 初始化max_reach为 0，表示初始时能到达的最远下标是 0；
2. 遍历数组的每个下标i：
   • 若当前下标i超过了max_reach，说明无法到达该位置，直接返回false；
   • 更新max_reach为【当前max_reach】与【i + nums[i]（当前位置能跳到的最远下标）】的较大值；
   • 若max_reach已覆盖最后一个下标（n-1），直接返回true（提前终止，提升效率）；
3. 遍历结束后（仅当数组长度为 1 时触发），返回true。

Python代码：

from typing import List class Solution: def canJump(self, nums: List[int]) -> bool: """ 判断是否能从数组第一个位置跳到最后一个位置 :param nums: 整数数组，nums[i] 表示在第 i 个位置可以跳跃的最大长度 :return: 能否到达最后一个位置，布尔值 """ # 边界情况1：数组为空，直接返回False（题目中nums通常非空，仅做鲁棒性处理） if not nums: return False # 边界情况2：数组只有1个元素，已经在最后位置，直接返回True if len(nums) == 1: return True max_reach = 0 # 记录当前能到达的最远下标 n = len(nums) # 遍历数组（无需遍历到最后一个元素，因为只要能到达倒数第二个的最远覆盖最后一个即可） for i in range(n - 1): # 若当前下标超过了最远可达范围，说明无法到达该位置，更无法到终点 if i > max_reach: return False # 更新最远可达范围：当前位置能跳到的最远位置 = 当前下标 + 最大跳跃长度 max_reach = max(max_reach, i + nums[i]) # 提前终止：若最远可达范围已覆盖最后一个下标，直接返回True if max_reach >= n - 1: return True # 遍历结束后仍未覆盖最后一个下标，返回False return False # ------------------- 测试用例 ------------------- if __name__ == "__main__": solution = Solution() # 测试用例1：正常可到达 nums1 = [2, 3, 1, 1, 4] print(f"测试用例1 [{nums1}]：{'true' if solution.canJump(nums1) else 'false'}") # 测试用例2：无法到达（卡在下标3） nums2 = [3, 2, 1, 0, 4] print(f"测试用例2 [{nums2}]：{'true' if solution.canJump(nums2) else 'false'}") # 测试用例3：边界情况（数组长度为1） nums3 = [0] print(f"测试用例3 [{nums3}]：{'true' if solution.canJump(nums3) else 'false'}") # 测试用例4：边界情况（第一个元素直接覆盖最后一个） nums4 = [5, 1, 0, 0, 0] print(f"测试用例4 [{nums4}]：{'true' if solution.canJump(nums4) else 'false'}") # 测试用例5：全0数组（长度>1） nums5 = [0, 0, 0] print(f"测试用例5 [{nums5}]：{'true' if solution.canJump(nums5) else 'false'}")

LeetCode提交代码：

class Solution: from typing import List def canJump(self, nums: List[int]) -> bool: max_reach = 0 # 记录当前能到达的最远下标 n = len(nums) for i in range(n): # 若当前下标超过了最远可达范围，说明无法到达 if i > max_reach: return False # 更新最远可达范围（当前位置+最大跳跃长度） max_reach = max(max_reach, i + nums[i]) # 若最远可达范围已覆盖最后一个下标，直接返回true if max_reach >= n - 1: return True # 遍历完成后（仅当数组长度为1时会走到这里） return True

程序运行截图展示：

总结

本文探讨了跳跃游戏问题的贪心算法解法。给定非负整数数组nums，初始位于第一个下标，每个元素表示可跳跃的最大长度。算法通过维护当前能到达的最远下标max_reach来判断是否能到达终点：遍历数组时若当前下标超过max_reach则返回false，否则更新max_reach为当前位置能跳到的最大距离。当max_reach覆盖终点时提前返回true。该方法时间复杂度O(n)，空间复杂度O(1)，高效解决了该问题。