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。

算法步骤

1. 检查当前下标是否值为0，若是直接返回 true；
2. 标记当前下标为已访问（防止循环）；
3. 尝试向右跳 i + arr[i]，若合法且未访问，则递归；
4. 尝试向左跳 i - arr[i]，若合法且未访问，则递归；
5. 若两条路径均失败，恢复标记并返回 false。

3. 代码实现

package lc1306;

public class Solution {
    public boolean canReach(int[] arr, int start) {
        if (arr[start] == 0) {
            return true;
        }
        int temp = arr[start];
        int n=start + arr[start];
        if (n< arr.length - 1 && arr[n] != -1) {
            arr[start] = -1;
            if (canReach(arr, n)) {
                return true;
            }
            arr[start]=temp;
        }
        int m=start - arr[start];
        if (m > 0 && m< arr.length - 1 && arr[m] != -1) {
            arr[start] = -1;
            if (canReach(arr, m)) {
                return true;
            }
            arr[start]=temp;
        }
        return false;
    }
}

4. 代码优化说明

减少了冗余的边界判断，统一处理左右跳转逻辑，同时去掉了不必要的 temp 变量与恢复操作，直接用访问标记避免循环：

package lc1306;

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public boolean canReach(int[] arr, int start) {
        return dfs(arr, start, new HashSet<>());
    }

    private boolean dfs(int[] arr, int index, Set<Integer> visited) {
        // 越界 或 已访问过，直接返回 false
        if (index < 0 || index >= arr.length || visited.contains(index)) {
            return false;
        }

        // 到达目标值 0，返回 true
        if (arr[index] == 0) {
            return true;
        }

        // 标记为已访问
        visited.add(index);

        int val = arr[index];
        // 左右两个方向只要有一条路通，就返回 true
        return dfs(arr, index + val, visited) || dfs(arr, index - val, visited);
    }
}

5. 复杂度分析

• 时间复杂度：$O(n)$，每个下标最多访问一次；
• 空间复杂度：$O(n)$，递归栈深度最坏为数组长度。

6. 总结

• 核心思路是DFS 遍历 + 访问标记，利用数组原地修改标记访问状态；
• 优化后代码逻辑更简洁，通过短路 || 直接返回结果，减少了分支判断；
• 本题也可用 BFS 实现，思路一致，避免递归栈溢出风险。