LeetCode 55. Jump Game 题解

张开发
• 2026/4/20 3:29:55 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

LeetCode 55. Jump Game 题解
LeetCode 55. Jump Game 题解题目描述给定一个非负整数数组nums你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。示例 1输入nums [2,3,1,1,4] 输出true 解释可以先跳 1 步从下标 0 到 1, 然后跳 3 步到达最后一个下标。示例 2输入nums [3,2,1,0,4] 输出false 解释无论怎样总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 所以永远不可能到达最后一个下标。解题思路方法贪心算法思路维护一个变量max_reach表示当前能够到达的最远位置遍历数组中的每个位置i如果当前位置i超过了max_reach说明无法到达该位置返回false更新max_reach为max(max_reach, i nums[i])如果max_reach大于等于数组的最后一个下标返回true复杂度分析时间复杂度O(n)其中 n 是数组的长度。只需要遍历数组一次。空间复杂度O(1)只需要常数级的额外空间。代码实现方法贪心算法class Solution: def canJump(self, nums: List[int]) - bool: n len(nums) if n 0: return False if n 1: return True max_reach 0 for i in range(n): # 如果当前位置超过了能够到达的最远位置返回 false if i max_reach: return False # 更新能够到达的最远位置 max_reach max(max_reach, i nums[i]) # 如果能够到达或超过最后一个下标返回 true if max_reach n - 1: return True return False测试用例测试用例 1输入nums [2,3,1,1,4]输出true测试用例 2输入nums [3,2,1,0,4]输出false测试用例 3输入nums [0]输出true测试用例 4输入nums [2,0,0]输出true总结本题是贪心算法的经典问题主要考察对贪心思想的理解和应用。通过维护一个能够到达的最远位置我们可以高效地判断是否能够到达最后一个下标。贪心算法的核心思想是在每一步都做出当前情况下的最优选择从而希望最终得到全局最优解。在本题中我们的最优选择是尽可能地扩大能够到达的最远位置。这种方法不仅适用于跳跃游戏问题还可以应用于许多其他需要贪心策略的问题例如跳跃游戏 II、加油站问题等。掌握贪心算法的思想对于解决这类问题非常重要。

更多文章