1306. 跳跃游戏 III — 图搜索思路拆解1. 题目概述与建模题目给定一个非负整数数组arr和起始位置start当位于下标i时可以跳到i arr[i]或i - arr[i]不能越界。判断能否跳到任意一个值为 0的下标处。为什么要学这道题这道题的模式在真实系统中无处不在网页爬虫从种子 URL 出发沿着链接爬向新页面已爬过的不重复爬——这就是图的遍历。理解了这道题你就理解了爬虫的核心逻辑也是所有从 A 出发能否到达 B问题的通用解法。思考过程还原我第一次看到这道题脑子里先闪过贪心——Jump Game I 不是贪心吗但很快注意到一个关键细节这题可以往左跳。一旦能往左跳就可能出现环比如 0→3→0。有环的图遍历和树不一样需要 visited 记录走过的路否则会陷入死循环。这一步很关键是整道题的转折点。问题建模这道题在问什么从start出发能不能到达值为 0 的位置——这是图可达性问题。关键建模步骤把数组的每个下标看成一个节点把合法的跳跃看做边。节点: arr 的每个下标 i (0~n-1) 边: i → i arr[i] (向右跳) i → i - arr[i] (向左跳) 目标: 能否到达任意 arr[i] 0 的节点以上面的示例arr [4,2,3,0,3,1,2], start 5为例建模出来的图邻接表: 0 → 4 (04) 0是目标节点 1 → 3 (12), -1(越界) 3是目标节点 2 → 5 (23), -1(越界) 3 → 7(越界), 0 (3-3) 3是目标节点 4 → 8(越界), 1 (4-3) 5 → 6 (51), 4 (5-1) 6 → 8(越界), 4 (6-2)为什么这是图而不是树因为双向跳跃会造出环。例如5→4→1→3又从 3 的3-30可以跳回不到达。所以必须有 visited 记录走过的节点否则会死循环。✅到这里你应该能回答为什么这道题是图遍历问题而不是树遍历如果还说不清楚——树只有往下走的分支不会绕回来图可能有环所以需要 visited。2. 第一个思路DFS 递归2.1 为什么会想到递归想象一下你在商场找出口每到一个路口有两条路可选——往左走 arr[i] 步往右走 arr[i] 步。你会怎么做随便选一条走到底走不通就退回来换一条——这就是 DFS深度优先搜索。再来看为什么这题适合递归站在任何一个位置你做的事和下一步做的事完全一样——检查自己是不是 0然后往两个方向跳。这个自己做的事和子问题做的事相同的特征就是递归的味道。2.2 标准递归写法classSolution{unordered_setintpaths;// 记录走过的节点防止重复访问防环public:boolcanReach(vectorintarr,intstart){returndfs(arr,start);}booldfs(vectorintnums,inti){// 1. 越界检查无法跳到数组之外if(i0||inums.size())returnfalse;// 2. 已访问检查双向跳跃会成环走过的路不再走if(paths.count(i))returnfalse;// 3. 标记为已访问paths.insert(i);// 4. 目标检查值为 0 → 到达if(nums[i]0)returntrue;// 5. 往两个方向跳 —— 短路求值左边能到就不用看右边了boolretdfs(nums,inums[i])||dfs(nums,i-nums[i]);// 6. 回溯离开当前节点时取消标记erase 操作paths.erase(i);returnret;}};2.3 实现要点① 终止条件的顺序——为什么越界先于 visitedif(i0||inums.size())returnfalse;// 先检查越界if(paths.count(i))returnfalse;// 再检查已访问类比就像走迷宫——先看墙越界再看是不是走过的路口visited最后看是不是出口target。顺序很重要因为越界访问下标会导致段错误必须优先排除。② visited 为什么不能省最自然的写法是不加 visited——凭什么不能再走一遍但双向跳跃会造出回路5 → 4 → 1 → 3 → 0 从3可以跳回不到0但跳到了0附近不加 visited 的代码会在有环的图里死循环栈溢出或无限递归。一个很自然的想法如果能回溯岂不是所有路径都能探索到这个想法在枚举所有路径时是合理的比如输出所有解但这道题只问能不能到不需要回溯。③ erase 操作在可达性问题中是多余的看上面代码第 6 行paths.erase(i);// 回溯时取消标记这个 erase 没有错不会导致程序出错。但它做了不需要的事——因为这道题只问能不能到只要找到一条路就够了不需要恢复状态去尝试其他路径。问题类型erase 操作原因能否到达本题不需要erase找到一条路就够了所有可达路径必须 erase需要恢复状态尝试另一条路④ 数据结构选择还能更好吗上面代码用unordered_setint来记录已访问节点功能完全正确。但这里有一个值得思考的点这道题的下标是什么特点下标从0到n-1是连续的、非负的整数哈希表的优势是应对稀疏、非连续的键可这道题的键恰好是连续的到这里我们已经解决了核心问题。还有没有可以优化的地方如果确定下标范围连续且非负可以用数组替代哈希表——访问是 O(1)没有哈希计算开销// 替代写法用 vectorchar 替代 unordered_setvectorcharvisited(arr.size(),0);visited[i]1;// 标记visited[i]1;// 检查两种写法时间复杂度都是 O(n)都能 AC。数组版本在连续下标场景下更快代码也更直观。⑤ 短路求值||为什么比|更安全// 正确写法短路求值returndfs(nums,inums[i])||dfs(nums,i-nums[i]);// 不推荐的写法不是bug但不安全returndfs(nums,inums[i])|dfs(nums,i-nums[i]);类比面试时第一题答对了就不用看第二题了——短路求值就是这样左边能到就返回右边不执行。|则会两边都执行在有副作用的函数里可能出问题。2.4 完整优化版综合上面两个优化点去掉 erase 用 vector得到完整优化版classSolution{vectorcharvisited;// 用 vectorchar 替代 unordered_set下标连续场景更快public:boolcanReach(vectorintarr,intstart){visited.assign(arr.size(),0);returndfs(arr,start);}booldfs(constvectorintnums,inti){// 越界 → 已访问 → 目标三件套一步到位if(i0||inums.size()||visited[i])returnfalse;visited[i]1;// 标记已访问if(nums[i]0)returntrue;// 找到目标// 不需要 erase可达性判断找到一条路就够了returndfs(nums,inums[i])||dfs(nums,i-nums[i]);}};相比最初的版本少了unordered_set的引入少了 erase 回溯逻辑更干净。✅到这里你应该能回答为什么这道题的 DFS 必须加 visited而二叉树的遍历不需要如果还说不清楚——树只有一条路往下走无环图可以绕回来有环所以需要 visited 来打勾。3. 第二个思路BFS队列3.1 什么时候该想到 BFS想象一下往水里扔一颗石子涟漪一圈圈扩散开——最先碰到边缘的那圈涟漪走的步数最少。这就是 BFS广度优先搜索。触发 BFS 的信号题目问最少步数 → 必须用 BFS因为 DFS 不知道走了多远担心递归深度太大栈溢出→ BFS 是纯迭代安全这道题只问能否到达DFS 和 BFS 都能做但 BFS 是 DFS 的等效替代3.2 BFS 写法classSolution{public:boolcanReach(vectorintarr,intstart){queueintq;vectorcharvisited(arr.size(),0);q.push(start);visited[start]1;while(!q.empty()){intiq.front();q.pop();if(arr[i]0)returntrue;// 找到目标// 扩展邻居intlefti-arr[i];intrightiarr[i];if(left0!visited[left]){visited[left]1;q.push(left);}if(rightarr.size()!visited[right]){visited[right]1;q.push(right);}}returnfalse;}};3.3 实现要点① 为什么用队列FIFO类比排队买奶茶——先到的先做后到的后做。队列就是这样先入先出的数据结构保证了我们按层次一圈一圈往外搜。② visited 何时标记——入队时不是出队时// 正确在入队时立即标记 —— 防止重复入队visited[left]1;q.push(left);// ❌ 错误写法在出队时才标记可能导致同一个节点被多次入队类比一进门就拿号不是叫到号才拿号——否则同一个人可能拿两个号排两次队。入队时标记保证每个节点只进队一次。③ 边界检查顺序if(left0!visited[left])// 先检查越界再检查 visited为什么因为!visited[left]如果 left 是负数C 负数下标访问可能不会立即报错undefined behavior所以越界检查必须放在前面。3.4 DFS vs BFS 对比DFS递归BFS队列天然适合判断能否到达 / 枚举所有路径求最短路径 / 最少步数实现方式递归系统栈迭代显式队列最坏空间O(n)递归深度O(n)队列宽度栈溢出风险有n 很大时如 n100000无找到目标的顺序不确定深度优先逐层扩散可自然得到最短步数代码量较少稍多生活类比走迷宫一条路走到底再换涟漪扩散逐层搜索到这里你已经掌握了两种图的遍历方式——DFS 和 BFS。这比很多人第一次学的时候快多了。✅到这里你应该能一眼判断看到最少步数就想到 BFS看到能否到达就想到 DFS/BFS 都行。如果看到所有路径呢那就要 DFS 回溯加 erase。4. DFS 递归核心解析综合优化后的完整代码来自 2.4 节classSolution{vectorcharvisited;// vectorchar 替代 unordered_set下标连续场景更快public:boolcanReach(vectorintarr,intstart){visited.assign(arr.size(),0);returndfs(arr,start);}booldfs(constvectorintnums,inti){if(i0||inums.size()||visited[i])returnfalse;visited[i]1;if(nums[i]0)returntrue;returndfs(nums,inums[i])||dfs(nums,i-nums[i]);}};关键设计点回顾设计点选择原因visited 数据结构vectorchar下标连续且非负O(1) 访问erase 操作不需要可达性判断找到一条路就够了visited 位置类成员递归栈上所有调用共享短路求值||左子树找到就返回右子树不执行时间复杂度每个节点最多访问一次 →O(n)空间复杂度visited O(n) 递归栈 O(n) →O(n)5. 常见坑点与失败替代方案坑点一visited erase 在可达性问题中是多余的如果写了 erase代码在逻辑上仍然正确能 AC但这是多了一步不需要的操作。记住问题类型erase 操作原因能否到达本题不需要erase找到一条路就够了所有可达路径必须 erase需要恢复状态尝试另一条路坑点二BFS visited 必须在入队时标记// ❌ 错误在出队时标记 —— 可能导致重复入队q.push(left);intcurq.front();q.pop();// 此时 left 还没标记visited[left]1;坑点三越界检查和 visited 检查的顺序// ❌ 不安全先检查 visited 再越界负数下标会 undefined behaviorif(paths.count(i)||i0||in)returnfalse;// ✅ 正确越界优先if(i0||in||paths.count(i))returnfalse;6. 真实系统中的图遍历 识别清单真实工程场景网页爬虫从种子 URL 出发沿超链接爬取已爬过的 URL 不重复爬——完全一样的隐式图遍历问题社交网络可达性判断 A 能否通过好友关系触达 B六度理论——同样是图的连通性判断迷宫求解判断能否从起点走到终点——经典 DFS/BFS 应用核心认知这道题的核心不是选 DFS 还是 BFS而是认清这是图遍历问题——双向跳跃必成环visited 不可省。识别清单拿到一道新题看到这些信号要条件反射想到图遍历 visited可以双向移动左右、上下、前后移动规则由数组/矩阵的值决定隐式图问能否从 A 到达 B图可能有环双向移动 可能有回路数组/矩阵很大递归深度可能溢出模式迁移表题目问题类型关键区别1306 跳跃游戏 III图可达性找目标节点130. 被围绕的区域图遍历染色找所有边界连通区域133. 克隆图图遍历BFS/DFS需要克隆节点200. 岛屿数量图遍历连通分量找连通分量个数695. 岛屿的最大面积图遍历找最大连通区域面积279. 完全平方数图最短路BFS 求最少步数7. 小结两种方法核心一致都是图的遍历时间 O(n)空间 O(n)。DFS 递归代码简洁天然适合判断能否到达但有栈溢出风险BFS 迭代绝对安全还能顺便算出最短步数但代码稍长这道题教会我们的最重要的一件事双向跳跃 可能有环 visited 不可省。一旦认清这是图遍历剩下的就是套模板了。图遍历的两把刷子你已经握在手里了。下次看到从 A 出发能不能到 B的题你会条件反射想到 visited DFS/BFS——因为你理解了为什么不只是记住了怎么写。