045.贪心算法
作者：沉默王二
发布时间：2024-09-06T16:29:33.813+0800
二哥逼逼：昨天微信驳回了某跳动的背后小动作，真的挺欣慰的。但从此以后，某跳动公司就上了我的黑名单，真的够恶心的。不过，今天我们还是来继续学习 LeetCode，原来是跳跃游戏，目前 LeetCode 已经改成跳跃游戏 II 了，并且题目描述也改变挺大的。
题意
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处：
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
原题意
给你一个非负整数数组 nums，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
我只能说原题意比现在的题意更容易懂，不知道 LeetCode 为什么要改。😄
难度
中等
示例
示例 1:
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入: nums = [2,3,0,1,4]
输出: 2
提示：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
1 <= nums.length <= 104
0 <= nums[i] <= 1000
### 分析
这道题的关键在于理解跳跃次数，和每次的跳跃步长。
假如你在第 0 个位置，第 0 个位置的数是 2（num[0]=2），那就意味着你可以跳到 1 的位置，也可以跳到 2 的位置。最长是 2，端是 1，对吧？
由于 num[1]=3，num[2]=1，所以我们可以选择跳到 1 的位置，因为下一次我们可以跳的更远，比如说 num[1+3]，也就是 4 的位置，直接就跳到末尾了。
但如果我们选择跳到 2 的位置，虽然这次跳的远，但下一次只能跳到 num[2+1]，也就是 3 的位置。还需要再跳一步才能到达末尾。
换句话说，我们每次跳的时候，不一定非要跳最远，但需要跳到下一次可以跳最远的地方。
能明白吧？
那针对这道题，我们可以直接使用贪心算法来完成，贪心的目的就是下一次跳的更远。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
public int jump(int[] nums) {
int n = nums.length;
int end = 0;
int maxPosition = 0;
int steps = 0;
for (int i = 0; i < n - 1; i++) {
maxPosition = Math.max(maxPosition, i + nums[i]);
if (i == end) {
end = maxPosition;
steps++;
}
}
return steps;
}
代码很好理解，我甚至都不用加注释，大家一看就明白。
但本着初心，我们还是详细地加一下注释（😄）
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
public int jump(int[] nums) {
// 数组的长度
int n = nums.length;
// 结束位置
int end = 0;
// 最大位置
int maxPosition = 0;
// 跳跃次数
int steps = 0;
// 遍历数组
for (int i = 0; i < n - 1; i++) {
// 获取最大位置
maxPosition = Math.max(maxPosition, i + nums[i]);
// 如果当前位置等于结束位置
if (i == end) {
// 更新结束位置
end = maxPosition;
// 跳跃次数加 1
steps++;
}
}
return steps;
}
运行效率也非常高。
总结
做人不要太贪，但是做算法一定要贪，有时候，贪心能够给我们带来更加极致的效率，但是，每次贪心之后需要细细回味下，并给出贪心的证明，才能不断向上突破，写出更好的更加优秀的贪心。
力扣链接：https://leetcode.cn/problems/jump-game-ii/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 6100 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
这道题可以说完全重写了，给出 1 道大家完全都能掌握的题解（ 主要是理解贪心算法的底层逻辑）。
增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。