Leetcode 55: 跳跃游戏
问题描述：
给定一个非负整数数组 nums，其中 nums[i] 表示从下标 i 位置最多可以跳跃的最大步数。
判断是否可以从数组的第一个位置跳跃到最后一个位置。
适合面试的解法：贪心算法
核心思想
- 利用 贪心算法（Greedy Algorithm），记录当前能够跳到的最远位置，逐步验证是否可以到达终点。
- 每次遍历一个新的位置时，更新能够跳到的最远距离
farthest。 - 如果当前下标
i大于farthest，说明无法继续往后跳跃，从而直接返回false。
选择贪心算法的理由：
- 贪心算法在处理区间覆盖、不重叠区间等问题时非常高效。
- 时间复杂度为 (O(n))，只需要遍历一次数组，适合处理大规模输入，解决此问题是最优解法。
- 空间复杂度为 (O(1))，不依赖额外空间，代码简洁高效，非常适合面试。
如何快速 AC：贪心算法
解题步骤：
-
初始化最远可达距离
farthest为 0- 表示当前从起点出发，能够跳到的最远位置。
-
遍历数组：
- 对于当前下标
i，如果i > farthest，说明无法继续向后跳跃，返回false； - 否则，更新
farthest = max(farthest, i + nums[i])。
- 对于当前下标
-
验证是否可以到达终点：
- 如果遍历完数组，并且
farthest>= 最后位置的下标 (nums.length - 1)，说明可以到达最后位置，返回true。
- 如果遍历完数组，并且
代码模板：贪心算法
class Solution {public boolean canJump(int[] nums) {int farthest = 0; // 最远可达位置for (int i = 0; i < nums.length; i++) {if (i > farthest) {return false; // 当前下标无法被覆盖，直接返回 false}farthest = Math.max(farthest, i + nums[i]); // 更新最远可达位置if (farthest >= nums.length - 1) {return true; // 如果已经可以到达最后位置，立即返回 true}}return false; // 如果遍历完成，仍无法到达最后位置}
}
代码详细注释
class Solution {public boolean canJump(int[] nums) {// 初始化变量int farthest = 0; // 最远可达位置，从起点出发// 遍历数组for (int i = 0; i < nums.length; i++) {// 如果当前下标超出最远可达位置，无法继续前进if (i > farthest) {return false;}// 更新从当前下标出发能跳到的最远位置farthest = Math.max(farthest, i + nums[i]);// 贪心优化：一旦可以到达终点，立刻返回if (farthest >= nums.length - 1) {return true;}}// 遍历完成后，检查是否能够覆盖终点return false;}
}
复杂度分析
时间复杂度：
- 我们只遍历数组一次，计算最远可达位置，时间复杂度为 (O(n))。
空间复杂度：
- 不需要额外空间，空间复杂度为 (O(1))。
典型测试用例
示例 1：
输入：
nums = [2,3,1,1,4]
输出：
true
解释：从下标 0 出发，跳跃到最后位置可以按照以下顺序：
- 从 0 -> 1，跳跃 2 步；
- 从 1 -> 4，跳跃 3 步；
- 最终到达目的地。
示例 2：
输入：
nums = [3,2,1,0,4]
输出：
false
解释：无论如何跳跃，都会卡在下标 3，原因是 nums[3]=0，无法越过。
示例 3：
输入：
nums = [0]
输出：
true
解释：单独一个位置本身就是终点，无需跳跃。
示例 4：
输入：
nums = [1,1,1,1,1]
输出：
true
解释：每次跳跃一步，总能到达终点。
示例 5：
输入：
nums = [0,2]
输出：
false
解释：起点为 0，无法跳跃到下标 1。
如何快速 AC（面试技巧）
1. 抓住贪心思想的核心：
- 每一步只关注当前节点，通过更新最远可达位置来解决问题；
- 如果有任何节点无法被覆盖，直接返回
false，无需复杂逻辑。
2. 时间复杂度要贴合 Top 解法
- 贪心算法是最优解法，遍历数组一次，时间复杂度 (O(n))，是最佳的面试答案。
3. 优雅优化的返回条件
- 在遍历过程中，观察到
farthest >= nums.length - 1的位置时，可以直接返回true提前结束计算，展示对逻辑优化的掌握。
总结
适合面试的解法：贪心算法
- 时间复杂度 (O(n))，空间复杂度 (O(1))，是该问题的最优解法。
- 贪心解法通过不断记录最远可达位置，逻辑直观简洁，非常适合面试。
如何快速 AC：
- 清晰定义贪心策略： 通过记录
farthest不断扩展跳跃的覆盖范围； - 代码逻辑直观： 遇到不能覆盖的点直接返回
false，否则最终返回true； - 注重边界处理： 特殊输入如长度为 1 或存在无法越过的 0 需要特别考虑。
利用贪心算法的高效解法，你可以快速解决问题并展示逻辑能力，非常适合面试环境！
