LeetCode 1306. 跳跃游戏 III

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 阿里
标签
数组 深度优先搜索 广度优先搜索

题目描述

✅ 1306. 跳跃游戏 III

image-20260929080502852

image-20260929080502954

题意分析

从下标 start 出发，在位置 i 每次可以恰好向右或向左跳 arr[i] 步，落点只能是 i + arr[i] 或 i - arr[i]，不能越出数组。判断能否到达任意一个值为零的位置。

跳跃长度是固定步数，不是最多可以跳多少步。数组里存在零还不够，必须从起点可达；只求是否存在路线，不需要返回最少跳数或具体路径。

解法：BFS 可达性遍历

核心思路

[!blue]

把数组下标看成图节点，每个节点最多有两条出边，指向左右两个合法落点。到达同一下标后能够继续走的位置总是相同，不依赖之前的路线，因此搜索状态只需要当前位置。

从起点开始用队列逐个扩展所有可达位置。每次出队先判断该位置的值是否为零，是就立即成功；否则计算两条出边，将未越界且未发现的落点加入队列。

左右跳跃可能形成环，多个路线也可能汇入同一个位置。用 visited 记录已经安排处理的下标，并在入队时立即标记，保证它只被安排一次；重复到达并不会产生新的后继，不必再次搜索。

若存在到零的路线，沿路线的每一个下标都会从前一个已发现位置被加入，最终目标必然被访问。若队列耗尽仍未命中，就已经检查了整个可达集合，没有任何路线可达零。某一方向越界只表示那条边不可走，不影响另一方向或其他队列状态。

解题步骤

  1. 创建访问标记和队列，起点入队时立即标记。
  2. 取出一个下标，若对应值为零则返回真，这也涵盖起点本身为零。
  3. 分别计算左右落点，对每个合法且未访问的位置先标记再入队。
  4. 继续处理直到发现零，或队列为空后返回假。

代码实现

class Solution {
    public boolean canReach(int[] arr, int start) {
        int n = arr.length;
        boolean[] visited = new boolean[n];
        ArrayDeque<Integer> queue = new ArrayDeque<>();

        queue.offer(start);
        // 标记已发现状态，保证一个下标只安排一次。
        visited[start] = true;

        while (!queue.isEmpty()) {
            int idx = queue.poll();

            // 先检查出队位置，这也覆盖起点本身为零。
            if (arr[idx] == 0) {
                return true;
            }

            // 两个落点独立判界，一个方向无效不影响另一个。
            int next1 = idx + arr[idx];
            int next2 = idx - arr[idx];

            if (next1 >= 0 && next1 < n && !visited[next1]) {
                visited[next1] = true;
                queue.offer(next1);
            }

            if (next2 >= 0 && next2 < n && !visited[next2]) {
                visited[next2] = true;
                queue.offer(next2);
            }
        }

        return false;
    }
}

func canReach(arr []int, start int) bool {
    n := len(arr)
    visited := make([]bool, n)
    queue := make([]int, 0)
    queue = append(queue, start)
    // 标记已发现状态，保证一个下标只安排一次。
    visited[start] = true

    for head := 0; head < len(queue); head++ {
        idx := queue[head]
        // 先检查出队位置，这也覆盖起点本身为零。
        if arr[idx] == 0 {
            return true
        }
        // 两个落点独立判界，一个方向无效不影响另一个。
        next1 := idx + arr[idx]
        next2 := idx - arr[idx]
        if next1 >= 0 && next1 < n && !visited[next1] {
            visited[next1] = true
            queue = append(queue, next1)
        }
        if next2 >= 0 && next2 < n && !visited[next2] {
            visited[next2] = true
            queue = append(queue, next2)
        }
    }
    return false
}

复杂度分析

  • 时间复杂度：$O(n)$，每个下标最多处理一次，每次检查两条边。
  • 空间复杂度：$O(n)$，用于访问标记和队列。

关键点总结

[!green]

  • 两个方向都需要考虑，不能当成只向右的跳跃题。
  • 某个落点越界只表示这条边不能走。
  • 不记录层数，入队状态只需当前位置。

易错点总结

[!yellow]

  • 无 visited 反复走环：非零位置之间可能互相跳回。
  • 数组中有 0 就返回 true：还必须从 start 可达。
  • 一条边越界就整体返回 false：另一方向可能有效。
  • 忽略起点本身：start 对应 0 时应直接成功。

相似题目

题目 难度 关联与区别
841. 钥匙和房间 中等 同样从起点做可达性搜索，本题next边由数组值生成，原题由钥匙列表提供。
1345. 跳跃游戏 IV 困难 跳跃游戏系列，均把下标视作图节点。IV 增加同值位置间的跳转，并用 BFS 求最少步数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/69954704
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！