LeetCode 55 45：跳跃游戏与跳跃游戏 II - 贪心算法详解
文章目录
- 引言
- 1. LeetCode 55：跳跃游戏
- 问题描述
- 解法1：正向贪心算法
- 解法2：反向贪心算法
- 2. LeetCode 45：跳跃游戏 II
- 问题描述
- 贪心解法
- 算法图解
- 3. 核心技巧总结
- 4. 常见问题解答
- 结语
引言
跳跃游戏系列是LeetCode中经典的贪心算法问题，考察对数组遍历和最优策略的理解。本文将详细解析55题（跳跃游戏）和45题（跳跃游戏 II）的解决方案，通过图解和Java实现帮助读者掌握贪心算法的应用。
1. LeetCode 55：跳跃游戏
问题描述
给定一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。
示例：
输入: [2,3,1,1,4]
输出: true
解释: 从位置0跳1步到位置1，再从位置1跳3步到达最后一个位置。
解法1：正向贪心算法
核心思路： 维护当前能够到达的最远位置，遍历数组并实时更新这个值。
class Solution {public boolean canJump(int[] nums) {int maxReach = 0; // 当前能够到达的最远位置int n = nums.length;for (int i = 0; i < n; i++) {if (i > maxReach) return false;maxReach = Math.max(maxReach, i