C++实现LeetCode(55.跳跃游戏)

前言跳跃游戏Jump Game的题面很短给定一个非负整数数组nums你最初位于下标 0每次可以从下标i跳到任意i k1 k nums[i]问能否到达最后一个下标。它考察的不是模拟每一次跳跃而是能否把「所有可达位置」压缩成一个区间。常见的误解有三个。第一把它和 45 题「跳跃游戏 II」混为一谈55 题只问「能不能到」45 题问「最少几步到」后者的贪心需要分层计数。第二认为必须正好落在最后一个下标实际上跳跃可以越过末尾只要能到达或越过即可。第三用回溯或 BFS 枚举所有跳法在nums[i]很大时状态爆炸而本题有O(n)的贪心解。本文以 C17 实现先给出「最远可达下标」这一不变量再证明它为什么足够然后给出贪心与动态规划两种写法最后用 45 题的最少步数解做对照避免把两道题套错。一、核心不变量最远可达下标定义farthest为「当前已经确认可以到达的最大下标」。初始时站在 0所以farthest 0。从左到右扫描下标i如果i farthest说明i及其右侧都不可达可以立即判定失败。否则i可达从i最远能跳到i nums[i]用这个值更新farthest。如果farthest n - 1已经可以到达终点返回成功。这个贪心之所以成立依赖一个关键性质可达位置构成一段从 0 开始的前缀区间。因为从任意可达的i出发能落到i1到inums[i]之间的每一个下标步长可以取 1所以可达集合不会出现「中间断开」的洞。只要farthest覆盖到某处从 0 到该处的所有下标都可达。用归纳法表述扫描完下标i后[0, farthest]内的所有下标都可达且farthest是当前能确认的最大可达下标。初始i 0时成立。若i farthest则i可达从它出发能覆盖到i nums[i]取最大值后新区间仍然连续若i farthest则i不可达由于下标是按顺序扫描的后面只会更不可达直接失败。二、贪心实现// 适用于 C17#include algorithm#include iostream#include vectorbool canJump(const std::vectorint nums) {const int n static_castint(nums.size());if (n 1) return true; // 空数组或只有一个元素已在终点int farthest 0;for (int i 0; i n; i) {if (i farthest) return false; // 当前位置不可达// 用 long long 计算避免 i nums[i] 溢出const long long reach static_castlong long(i) nums[i];if (reach farthest) {farthest static_castint(std::minlong long(reach, n - 1));}if (farthest n - 1) return true;}return true;}int main() {std::vectorint nums {2, 3, 1, 1, 4};std::cout (canJump(nums) ? true : false) \n;std::vectorint blocked {3, 2, 1, 0, 4};std::cout (canJump(blocked) ? true : false) \n;return 0;}按标准语义推演第一组{2, 3, 1, 1, 4}i0时farthest2i1时可达reach4更新后farthest4已达到n-1返回true。第二组{3, 2, 1, 0, 4}i0时farthest3i1、i2、i3都可到达但nums[3]0无法推进i4时4 3返回false。代码里有两个防御性细节值得说明。n 1的提前返回处理了空数组和单元素数组单元素时起点就是终点答案恒为真。reach用long long计算是因为i nums[i]中两个int相加可能超过INT_MAX有符号整数溢出属于未定义行为undefined behavior, UB不能指望它「变成负数后自然失败」。把结果夹到n - 1也避免farthest无意义地增长。三、动态规划写法与对比同一问题可以用O(n^2)的 DP 表达思路更直白// 适用于 C17#include cstddef#include vectorbool canJumpDP(const std::vectorint nums) {const std::size_t n nums.size();if (n 0) return true;std::vectorbool reachable(n, false);reachable[0] true;for (std::size_t i 0; i n; i) {if (!reachable[i]) continue;const std::size_t step static_caststd::size_t(nums[i]);// 防止 i step 溢出先把上界夹到 n - 1const std::size_t limit (step n - 1 - i) ? (n - 1) : (i step);for (std::size_t j i 1; j limit; j) {reachable[j] true;}if (reachable[n - 1]) return true;}return reachable[n - 1];}这里n - 1 - i不会下溢因为循环内i n - 1。当step大于等于剩余距离时上界直接取n - 1避免i step在size_t上回绕。nums[i]按题意非负若输入含负数static_caststd::size_t会得到巨大值代码会把它当成「能跳到末尾」因此使用前应校验输入。两种写法的对比维度贪心动态规划时间O(n)最坏O(n^2)空间O(1)O(n)思路维护最远可达标记每个位置可达性适用只需判断可行性需要知道每个位置是否可达如果题目追问「哪些位置可达」DP 的布尔数组更直接只问终点贪心足够。四、与 45 题「最少跳跃次数」的区别45 题要求最少步数贪心需要「分层」把当前一步能覆盖的区间看作一层层内所有位置都走一步可达层边界用currentEnd表示。// 适用于 C17#include algorithm#include vectorint minJumps(const std::vectorint nums) {const int n static_castint(nums.size());if (n 1) return 0;int jumps 0;int currentEnd 0; // 当前这一步能到达的最右边界int farthest 0; // 再走一步能到达的最右边界for (int i 0; i n - 1; i) {const long long reach static_castlong long(i) nums[i];farthest std::maxlong long(farthest, std::minlong long(reach, n - 1));if (i currentEnd) { // 当前层扫描完毕jumps;currentEnd farthest;if (currentEnd n - 1) break;}}return jumps;}注意std::maxlong long的两个实参都必须是long longfarthest是int时会参与模板推导显式指定模板参数后int会被提升返回类型是long long再赋回int需要窄化转换。上面的写法把farthest声明为int赋值时会发生隐式窄化虽然值已被夹在n-1内不会溢出但更严谨的写法是把farthest也声明为long long最后再转换。这类细节不影响算法却影响代码是否经得起静态检查。55 题不能用 45 题的返回值直接判断45 题保证输入一定可达55 题可能不可达minJumps在不可达时会返回一个没有意义的值。两题的输入约束不同不能互相套用。常见坑点1. 把 55 题当成 45 题❌ 直接返回最少步数或认为步数为 0 就不可达。 ✅ 55 题只判断能否到达不可达时立即返回false不要计算步数。2. 循环不检查可达性❌for (int i 0; i n; i) farthest std::max(farthest, i nums[i]);把不可达位置也用来更新。 ✅ 先判断i farthest就失败再更新farthest。3. 忘记单元素数组❌if (nums[0] 0) return false;对{0}返回错误结果。 ✅ 先处理n 1起点即终点时返回true。4. 认为不能越过终点❌ 限制i nums[i] n把「跳过末尾」当成非法。 ✅ 跳跃可以越过最后一个下标只要farthest n - 1即可。5.i nums[i]溢出❌ 直接用int相加nums[i]接近INT_MAX时溢出属于 UB。 ✅ 用long long计算或先把步长夹到n - 1 - i。6. 动态规划里size_t回绕❌for (std::size_t j i 1; j i nums[i]; j)i nums[i]可能回绕成小值。 ✅ 先算limit并夹到n - 1再写循环条件。7. 修改输入数组❌ 把nums[i]改成「剩余可达距离」以便递推破坏调用方数据。 ✅ 用局部变量维护farthest保持入参只读。8. 用 BFS 枚举所有落点❌ 对每个位置把1..nums[i]全部入队最坏情况状态数爆炸。 ✅ 利用可达区间的连续性只维护最远边界。总结题目问什么贪心维护返回值55 跳跃游戏能否到达末尾farthestbool45 跳跃游戏 II最少几步currentEndfarthest步数55 题的关键不是「怎么跳」而是「最远能到哪」。只要可达位置始终是一段连续前缀维护一个最远下标就足以判定终点是否被覆盖。把 55 与 45 的问法、边界和返回值分清再注意int求和的溢出这道题就不会在细节上失分。