LeetCode 55. Jump Game 题解Go 语言贪心算法判断能否跳到数组末尾【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文基于 LeetCode-Go 仓库中 leetcode/0055.Jump-Game/README.md 的官方题解结合仓库内对应的 Go 源码实现 与 表驱动测试用例系统讲解经典贪心问题 Jump Game跳跃游戏的题意、核心思路、正确性证明、复杂度分析以及在本地运行测试的完整方法。读完本文你将掌握维护最远可达下标这一贪心套路并能在 O(n) 时间内解决这类能否到达终点的跳跃问题同时能够独立在本仓库中复现运行结果。一、题目回顾非负整数数组上的跳跃判定原题描述如下Given an array of non-negative integers, you are initially positioned at the first index of the array.Each element in the array represents your maximum jump length at that position.Determine if you are able to reach the last index.题目大意给定一个非负整数数组你最初位于数组的第一个位置下标 0。数组中的每个元素代表在该位置最多可以跳跃的长度可以是 0 到该值之间的任意步数判断你是否能够到达数组的最后一个位置。需要特别强调的是两个约束边界数组元素非负也就是说每个位置都可能出现0每个元素表示的是最大跳跃长度实际跳多少步由你决定这为贪心策略留下了空间。仓库题解leetcode/0055.Jump-Game/README.md将题意概括为给出一个非负数组要求判断从数组 0 下标开始能否到达数组最后一个位置。二、示例拆解两个典型用例原题给出了两个极具代表性的示例一个可达、一个不可达恰好覆盖了贪心判断的两种结果。示例 1可以到达末尾Input: [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.过程说明位于下标 0 时最大能跳 2 步选择只跳 1 步到达下标 1下标 1 处的值为 3最大可跳 3 步直接跳到最后一个下标 4成功到达。示例 2无法到达末尾Input: [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.过程说明下标 3 处的值为0也就是说无论之前怎么选择一旦到达下标 3 就无法继续前进而它最大只能跳到下标 3 本身向后无法到达下标 4因此永远无法到达最后一个位置。从结构上看示例 2 是经典的零值陷阱数组中存在一个0并且这个0之前没有任何位置能够越过它导致路径被切断。三、核心解题思路贪心维护最远可达下标本题属于经典的贪心问题。仓库题解给出的核心思路可以提炼为三点可达范围扩展如果某一个作为「起跳点」的格子可以跳跃的距离是n那么表示后面n个格子都可以作为「起跳点」。也就是说从该格子出发下标i1到in之间的所有位置都是可达的。不断更新最远距离对每一个能作为「起跳点」的格子都尝试跳一次把「能跳到的最远距离maxJump」不断更新maxJump max(maxJump, i nums[i])。断点判断如果中间有一个下标i比maxJump还要大说明在这个点和maxJump之间已经连不上了有些点不能到达最后一个位置直接返回false如果遍历完整个数组都没有出现这种情况说明可以一直跳到最后返回true。用更直观的话说我们在遍历数组的同时始终维护一个从起点出发、经过已扫描位置能到达的最远下标。只要当前下标没有超出这个最远可达范围就说明当前位置是可达的进而可以用当前位置的跳跃能力继续扩大这个范围。这本质上是一个区间逐步右推的过程属于典型的贪心也可视作隐式的区间合并 / BFS 最远层扩展策略。四、Go 语言实现仓库源码逐行解读仓库中本题的完整实现位于 leetcode/0055.Jump-Game/55.%20Jump%20Game.go与题解文档中的代码完全一致func canJump(nums []int) bool { n : len(nums) if n 0 { return false } if n 1 { return true } maxJump : 0 for i, v : range nums { if i maxJump { return false } maxJump max(maxJump, iv) } return true } func max(a int, b int) int { if a b { return a } return b }对关键分支与边界条件的解读代码片段作用与边界处理if n 0 { return false }空数组不存在最后一个位置按不可达处理该分支更多是为了防御性健壮性实际 LeetCode 输入一般非空if n 1 { return true }数组只有一个元素时起点即终点天然可达maxJump : 0初始化当前最远可达下标。起点下标 0 本身可达因此初始值 0 是合理的if i maxJump { return false }核心剪枝当前下标已经超出了此前所有位置能到达的最远范围说明中间存在断点不可达maxJump max(maxJump, iv)贪心更新当前位置下标i加上其最大跳跃长度v与历史最远值取较大者一个值得注意的细节即使当前位置的值v为 0只要maxJump已经覆盖了它程序也不会立即返回false——它只是无法继续扩大可达范围而已最终结果取决于后续下标是否仍然被覆盖。这与示例 2 中的零值陷阱恰好呼应下标 3 的 0 本身不致命致命的是没有任何一个之前的位置能跨过下标 3于是在遍历到下标 4 时发现4 maxJump(3)返回false。此外仓库中该题代码还附带了同包内独立的max辅助函数55. Jump Game.go。由于本题实现位于独立的 leetcode 包内max与包内其他题目互不冲突。五、为什么贪心是正确的不变量与复杂度分析贪心解法成立的关键在于一个不变量遍历到下标i时maxJump恰好等于从起点出发、仅借助[0, i]范围内位置的可达最远下标。归纳基础i 0时maxJump 0起点可达成立。归纳递推若处理完[0, i-1]后maxJump ≥ i说明i可达此时用i nums[i]与旧值取 max可达范围单调不减不变量保持。断点判定一旦出现i maxJump说明i不可达而数组从左到右连续推进因此之后的所有下标同样不可达直接返回false正确。时间复杂度单次线性扫描O(n)。空间复杂度仅使用常数个变量O(1)。这也正是该解法能够达到题解文档所述runtime beats 100%量级的原因——没有任何多余的分配或二次扫描。六、测试验证仓库表驱动测试用例仓库为本题编写了表驱动table-driven测试位于 leetcode/0055.Jump-Game/55.%20Jump%20Game_test.go共覆盖 4 组输入输出输入数组期望输出覆盖点[2,3,1,1,4]true原题示例 1正常可达[3,2,1,0,4]false原题示例 2零值陷阱导致不可达[]false空数组边界[0]true单元素边界起点即终点测试通过question55结构体把参数para55{one []int}与期望答案ans55{one bool}打包循环调用canJump(p.one)后与期望比对不一致时通过t.Fatalf立即报错并输出实际输入输出例如got : canJump(p.one) if got ! a.one { t.Fatalf(input: %v, expected: %v, got: %v, p.one, a.one, got) } fmt.Printf(【input】:%v 【output】:%v\n, p, got)其中空数组与单元素数组两组用例正好验证了第四节中n 0与n 1两个边界分支的处理逻辑。七、在本地运行与验证本仓库使用 Go module 管理依赖见 go.modGo 版本要求 1.19且项目根目录提供了统一的测试脚本 gotest.sh其核心命令为go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...针对本题可在仓库根目录单独运行go test -v -run Test_Problem55 ./leetcode/0055.Jump-Game/运行后可以看到针对四组用例的【input】/【output】输出以及类似PASS的最终结果。若希望看到单测覆盖率可加上-cover参数本项目在根目录执行go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...即可为全部 LeetCode 题解生成统一的覆盖率文件生成结果写入根目录 coverage.txt。八、总结与同类问题联想Jump Game 是贪心 可达区间类问题的入门经典本题的核心套路可以概括为一句话遍历过程中维护最远可达下标一旦当前位置超出该范围即宣告不可达。从源码结构看本仓库还收录了跳跃类题目的多个变体例如 45. Jump Game II最少步数到达末尾、1306. Jump Game III从指定起点按值跳跃、1696. Jump Game VI带分数的跳跃等。掌握本题的贪心思想后阅读这些变体题解将更加轻松。若需继续查阅相关题解可在仓库的 leetcode 目录下按题号定位对应文件夹每个题目目录下均包含 README 题解、.go实现与_test.go测试三件套。要点速览判断标准能否从下标 0 借助各位置最大跳跃长度到达最后下标核心变量maxJump当前最远可达下标终止条件i maxJump即不可达遍历结束则可达复杂度时间 O(n)空间 O(1)边界空数组返回false单元素数组返回true。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考