6-102-(LeetCode-55) 跳跃游戏
1. 题目
读题
https://leetcode.cn/problems/jump-game/
考查点
这道题主要考查的是贪心算法的应用，
- 即在每一步选择最优的局部解，从而达到全局最优的目的。
- 贪心算法通常用于解决一些最优化问题，如最小生成树、单源最短路径、任务调度等。
-
2. 解法
思路
一个可能的解决方案是使用贪心算法，即每次选择能跳到最远的位置。具体步骤如下：
- 初始化一个变量maxReach，表示当前能跳到的最远位置，初始值为0。
- 遍历数组中的每个元素，对于每个元素i，更新maxReach为max(maxReach, i + nums[i])，即当前位置加上能跳的长度和之前的最远位置中的较大值。
- 如果maxReach >= nums.length - 1，说明能够到达最后一个下标，返回true。
- 如果i > maxReach，说明当前位置已经超过了能跳到的最远位置，无法继续前进，返回false。
具体实现
class Solution {
public boolean canJump(int[] nums) {
int maxReach = 0; //当前能跳到的最远位置
for (int i = 0; i < nums.length; i++) {
if (maxReach >= nums.length - 1) return true; //能够到达最后一个下标
if (i > maxReach) return false; //当前位置超过了能跳到的最远位置
maxReach = Math.max(maxReach, i + nums[i]); //更新最远位置
}
return false;
}
}