LeetCode 每日一题笔记0. 前言日期2026.05.17题目1306. 跳跃游戏 III难度中等标签数组、深度优先搜索、广度优先搜索1. 题目理解问题描述给定一个非负整数数组arr从下标start出发每次可以从下标i跳到i arr[i]或i - arr[i]。你无法跳出数组边界。判断是否能够跳到数组中任意一个值为 0 的下标。示例输入arr [4,2,3,0,3,1,2],start 5输出true解释路径5 → 4 → 1 → 3下标3的值为0。2. 解题思路核心观察这是一个典型的图遍历问题每个下标是节点跳跃规则是边需避免重复访问否则会无限递归/循环只要遍历过程中遇到值为0的节点即可返回true。算法步骤检查当前下标是否值为0若是直接返回true标记当前下标为已访问防止循环尝试向右跳i arr[i]若合法且未访问则递归尝试向左跳i - arr[i]若合法且未访问则递归若两条路径均失败恢复标记并返回false。3. 代码实现packagelc1306;publicclassSolution{publicbooleancanReach(int[]arr,intstart){if(arr[start]0){returntrue;}inttemparr[start];intnstartarr[start];if(narr.length-1arr[n]!-1){arr[start]-1;if(canReach(arr,n)){returntrue;}arr[start]temp;}intmstart-arr[start];if(m0marr.length-1arr[m]!-1){arr[start]-1;if(canReach(arr,m)){returntrue;}arr[start]temp;}returnfalse;}}4. 代码优化说明减少了冗余的边界判断统一处理左右跳转逻辑同时去掉了不必要的temp变量与恢复操作直接用访问标记避免循环packagelc1306;importjava.util.HashSet;importjava.util.Set;publicclassSolution{publicbooleancanReach(int[]arr,intstart){returndfs(arr,start,newHashSet());}privatebooleandfs(int[]arr,intindex,SetIntegervisited){// 越界 或 已访问过直接返回 falseif(index0||indexarr.length||visited.contains(index)){returnfalse;}// 到达目标值 0返回 trueif(arr[index]0){returntrue;}// 标记为已访问visited.add(index);intvalarr[index];// 左右两个方向只要有一条路通就返回 truereturndfs(arr,indexval,visited)||dfs(arr,index-val,visited);}}5. 复杂度分析时间复杂度O ( n ) O(n)O(n)每个下标最多访问一次空间复杂度O ( n ) O(n)O(n)递归栈深度最坏为数组长度。6. 总结核心思路是DFS 遍历 访问标记利用数组原地修改标记访问状态优化后代码逻辑更简洁通过短路||直接返回结果减少了分支判断本题也可用 BFS 实现思路一致避免递归栈溢出风险。
