055.跳跃游戏
作者：沉默王二
发布时间：2024-11-21T16:55:44.047+0800
鲁迅曾说，人生就是不断地跳跃，不断地前进。但在遇到事情的时候，尽量冷静一点，不要轻易做出决定，给自己一点缓冲的时间，因为紧急情况下做出的决定往往都是欠缺考虑的。好，今天继续坚持来一道 LeetCode 题解，第 55 题——跳跃游戏。
题意
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。如果可以，返回 true；否则，返回 false。
难度
中等
示例
示例1：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例2：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0， 所以永远不可能到达最后一个下标。
### 分析 1
看到这题，很容易联想到045.跳跃游戏② ，但作为事后诸葛亮来看，这道题比 45 题还要简单，因为我们不需要知道到达最后一个位置的最小跳跃次数，只需要知道是否能到达最后一个位置即可。
比较维度
55 跳跃游戏
45 跳跃游戏 II
目标
判断是否可以跳到最后一个位置。
求跳到最后一个位置所需的最少跳跃次数。
输出
true/false。
一个整数。
优化重点
尽早判断是否能够到达最后一个位置，优化路径的可达性检测。
在可达路径中寻找最优跳跃方案，优化跳跃次数。
跳跃策略
只需确保路径中没有不可达的点即可。
每一步都需要计算当前最优跳跃位置，以减少跳跃次数。
适用算法
贪心算法（判断最远可达范围）。
贪心算法（逐步扩展范围，按层次计算最优跳跃）。
这道题目并不需要我们考虑太多，只需要抓住一点—— “当前位置一定小于等于最远能跳的位置” 就可以解决这个问题了，因为如果要达到一个位置，在到达那个位置之前，能跳的最远位置一定大于等于它。
换句话说，你只管跳，跳不到就 return false。
这样，一道 “中等题” 便成了简单题，轻轻松松几行代码就可以拿下。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
class Solution {
public boolean canJump(int[] nums) {
int maxPos = 0;
for(int i = 0;i < nums.length;i++){
if(i > maxPos){//观察当前位置是否能跳
return false;
}
maxPos = Math.max(maxPos,i + nums[i]);//更新能跳的最远位置
}
return true;
}
}
以 nums = [2, 3, 1, 1, 4] 为例：
效率自然是没得说：
总结
解出这道题之后，你就会发现，原来的 中等 题只是“徒有其表”，就这样，保持下去，通过不断地刷题来训练我们的思维，虽然说总会有难题存在，但解题的思路也会随之增加，能力也会得到不断地提升。
力扣链接：https://leetcode.cn/problems/jump-game/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 6600 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
这道题可以说完全重写了，给出 1 道大家完全都能掌握的题解（暴力解法）。
增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。