LeetCode 1345. 跳跃游戏 IV

2022-12-26 HGNULB 约 11 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 1345. 跳跃游戏 IV

题意分析

从下标 0 出发走到下标 n - 1，每一步有三种走法：走到 i + 1、走到 i - 1（都必须在数组范围内）、或者跳到任意满足 arr[j] == arr[i] 且 j != i 的下标 j。问最少几步。

「每一步代价都是 1」是第一个信号：这是无权图上的最短路，不需要优先队列，按层展开即可。

「可以走到 i - 1」是第二个信号，而且很关键——路径可以往回走。这意味着不存在「从左到右一次递推」的无后效性顺序，任何一维 DP 的尝试都会失败。比如 arr = [7,6,9,6,9,6,9,7]，最优解是从下标 0 直接同值跳到下标 7，只要 1 步；而按下标从左往右推的做法根本表达不出这种「一步跨到终点」的跳跃。

「同值下标之间两两可达」是第三个信号，也是全题唯一的难点。约束 1 <= arr.length <= 5 * 10^4，若某个值出现了 m 次，这一组内部就有 $O(m^2)$ 条边；极端情况如 arr 全为 0 时边数达到 $1.25 \times 10^9$，显式建图必然爆炸。所以「同值边」只能隐式表达，而且必须保证每条边总共只被考虑常数次。

边界：n == 1 时起点即终点，答案 0。另外由于 i ± 1 这类边把所有下标串成了一条链，图必然连通，理论上永远不会出现无解，代码里的 -1 分支只是形式上的兜底。

解法：BFS + 同值下标分组

核心思路

把下标当作图的节点，三种走法当作边，问题就是「从节点 0 到节点 n-1 的最短路」。所有边权为 1，BFS 逐层扩展时第一次访问到某个节点，此时的层号就是它的最短距离，这是 BFS 求无权最短路的基本性质。

直接建图不可行（同值边有 $O(n^2)$ 条），所以改成隐式邻接：预处理一个哈希表 indices，把每个值映射到它出现过的全部下标列表。扩展节点 cur 时，邻居就是 cur - 1、cur + 1 以及 indices[arr[cur]] 里的所有下标。这样建表只要 $O(n)$，不需要真的把边存下来。

但光这样还不够。如果 arr 全为 0，那么每个节点被扩展时都要遍历一遍长度为 n 的下标列表，总工作量仍是 $O(n^2)$，虽然答案正确但会超时。

关键观察：某个值的下标组一旦被任何一个节点展开过，组内所有下标就都已经被标记访问并入队（距离已确定）；之后再有同值节点来展开这一组，不可能产生任何新节点，纯属浪费。因此展开完立刻把这个值从哈希表里删掉。

这一删把总代价摊平了：所有值组的大小之和恰好是 n，而每组只会被完整扫描一次，于是同值边的总处理量是 $O(n)$；加上 i ± 1 的 $2n$ 条边，整体线性。这就是本题从「能过样例」到「能过大数据」的分水岭。

不变量：队列中同一层的所有下标到起点的距离相等；visited[i] 为真表示 i 的最短距离已经确定（而不是「已经处理完」）。访问标记必须在入队时设置，否则同一层里多个节点会把同一个下标重复塞进队列。

步数的记法采用「按层计数」：外层 while 每处理完一整层，steps 加一；从队列取出节点时若它是 n - 1，直接返回当前的 steps。起点在第 0 层，steps 初值 0，语义自洽。

解题步骤

特判 n == 1：起点即终点，返回 0。这一分支其实会被主循环第一轮自然覆盖（第一次出队的就是 n-1），保留它只是让边界更醒目。

预处理同值分组：遍历一遍数组，把每个值映射到它的下标列表。必须先建完整张表再开始 BFS，否则展开时看不到后面的同值下标。

初始化 BFS：队列放入 0，visited[0] = true，steps = 0。

按层循环：每轮先记下当前队列长度 size，只处理这 size 个节点，它们构成完整的一层；这一层处理完再让 steps 自增。

出队即判终点：取出 cur 后立刻检查 cur == n - 1，命中就返回 steps。判断放在出队而不是入队，是为了让返回值与「按层计数」的口径一致。

扩展三类邻居：cur - 1、cur + 1、以及同值组内的全部下标。统一走一个 offer 辅助函数，里面做越界与已访问检查，检查通过就立即置位 visited 并入队。

删除已展开的值组：扫完 indices[arr[cur]] 后把这个键删掉。这一步不影响正确性，只影响复杂度，但少了它大数据必超时。

队列耗尽返回 -1：形式上的兜底，实际因为 i ± 1 边使图连通而不会走到。

以 arr = [100, -23, -23, 404, 100, 23, 23, 23, 3, 404] 走一遍，n = 10，目标下标 9。

预处理得到：100 -> [0, 4]、-23 -> [1, 2]、404 -> [3, 9]、23 -> [5, 6, 7]、3 -> [8]。初始队列 [0]，steps = 0。

第 0 层（steps = 0）：取出 0，不是终点。offer(-1) 越界丢弃；offer(1) 入队。展开值组 100 -> [0, 4]：0 已访问跳过，4 入队；随后删除键 100。本层结束，steps 变成 1，队列为 [1, 4]。

第 1 层（steps = 1）：取出 1，offer(0) 已访问，offer(2) 入队；值组 -23 -> [1, 2] 两个都已访问，删除键 -23。取出 4，offer(3) 入队，offer(5) 入队；值组 100 已被删除，这里直接跳过——如果没删，就要白白再扫一遍 [0, 4]。本层结束，steps 变成 2，队列为 [2, 3, 5]。

第 2 层（steps = 2）：取出 2，两个邻居都已访问。取出 3，offer(2)、offer(4) 均已访问；展开值组 404 -> [3, 9]，下标 9 入队，删除键 404。取出 5，offer(6) 入队；展开值组 23 -> [5, 6, 7]，6 刚入队已标记、7 入队，删除键 23。本层结束，steps 变成 3，队列为 [9, 6, 7]。

第 3 层（steps = 3）：取出 9，等于 n - 1，返回 3。

对应的路径是 0 -> 4（同值 100）-> 3（左移）-> 9（同值 404），恰好三步。注意这条路径中间向左走了一格，正是「不能用从左往右的 DP」的直观例证。

代码实现

class Solution {
    public int minJumps(int[] arr) {
        int n = arr.length;
        if (n == 1) {
            return 0;
        }

        // 先把同值下标全部归类，避免扩展时全数组查找。
        Map<Integer, List<Integer>> indices = new HashMap<>();
        for (int i = 0; i < n; i++) {
            indices.computeIfAbsent(arr[i], key -> new ArrayList<>()).add(i);
        }

        Deque<Integer> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[n];
        queue.offer(0);
        visited[0] = true;

        int steps = 0;
        while (!queue.isEmpty()) {
            // 先固定本层节点数，处理完这一层再让步数自增。
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                if (cur == n - 1) {
                    return steps;
                }

                offer(queue, visited, cur - 1);
                offer(queue, visited, cur + 1);

                List<Integer> same = indices.get(arr[cur]);
                if (same != null) {
                    for (int next : same) {
                        offer(queue, visited, next);
                    }

                    // 该值组内所有下标此刻都已确定距离，删掉它，
                    // 把同值边的总扫描量从 O(n^2) 摊到 O(n)。
                    indices.remove(arr[cur]);
                }
            }
            steps++;
        }

        return -1;
    }

    private void offer(Deque<Integer> queue, boolean[] visited, int idx) {
        // 访问标记必须在入队时置位，否则同一层里同一下标会被重复入队。
        if (idx < 0 || idx >= visited.length || visited[idx]) {
            return;
        }

        visited[idx] = true;
        queue.offer(idx);
    }
}

func minJumps(arr []int) int {
    n := len(arr)
    if n == 1 {
        return 0
    }

    // 先把同值下标全部归类，避免扩展时全数组查找。
    indices := make(map[int][]int)
    for i, num := range arr {
        indices[num] = append(indices[num], i)
    }

    queue := []int{0}
    visited := make([]bool, n)
    visited[0] = true

    offer := func(idx int) {
        // 访问标记必须在入队时置位，否则同一层里同一下标会被重复入队。
        if idx < 0 || idx >= n || visited[idx] {
            return
        }
        visited[idx] = true
        queue = append(queue, idx)
    }

    steps := 0
    for len(queue) > 0 {
        // 先固定本层节点数，处理完这一层再让步数自增。
        size := len(queue)
        for i := 0; i < size; i++ {
            cur := queue[i]
            if cur == n-1 {
                return steps
            }

            offer(cur - 1)
            offer(cur + 1)

            for _, next := range indices[arr[cur]] {
                offer(next)
            }
            // 该值组内所有下标此刻都已确定距离，删掉它，
            // 把同值边的总扫描量从 O(n^2) 摊到 O(n)。
            delete(indices, arr[cur])
        }
        queue = queue[size:]
        steps++
    }

    return -1
}

复杂度分析

时间复杂度：$O(n)$。预处理分组一遍 $O(n)$；BFS 中每个下标最多入队一次，i ± 1 边共 $2n$ 条；每个值组只会被完整扫描一次而所有组的大小之和为 n，所以同值边的总处理量也是 $O(n)$。「用完即删」正是把这一项从 $O(n^2)$ 压到 $O(n)$ 的原因。

空间复杂度：$O(n)$。哈希表存下全部 n 个下标，visited 数组长度为 n，队列中同时最多容纳 n 个下标，三者都与数组长度同阶。

关键点总结

边权全为 1 就用 BFS：看到「最少步数」且每步代价相同，直接按层展开，不要上优先队列——多一个 $\log$ 不说，还会被追问「为什么要用堆」。

大规模同值边要隐式表达 + 用完即删：这是本题的核心技巧，也是一类通用手法：当某种邻接关系是「等价类内部两两相连」时，把类当成中转节点或展开后立即销毁，都能把 $O(n^2)$ 边压成 $O(n)$。

visited 在入队时置位，不是出队时：出队才标记会让同一层的多个节点把同一下标重复入队，队列规模在极端输入下爆炸。这是 BFS 最常见的性能陷阱。

按层计数与逐点记距离二选一：本题用 size = queue.size() 锁定层边界并在层末自增 steps，就不需要额外的 dist 数组；两种写法都对，但混用必然把步数算错一位。

可以向左走 ⇒ 一维 DP 不成立：题目允许 i - 1 和跨越式同值跳跃，状态之间没有单向的拓扑序，只能按最短路来处理。识别出这一点比写出代码更重要。

面试视角：面试官最想听到的一句话是「同值边最坏有 $O(n^2)$ 条，我用展开后清空值组把它降到 $O(n)$」。能主动给出全 0 数组这个反例，基本就拿下了这题。

易错点总结

展开同值组后不删除该键：arr 全为 0 且 n = 5 * 10^4 时，每个出队节点都要遍历长度 n 的下标列表，约 $2.5 \times 10^9$ 次操作，结果虽正确但必然超时。

visited 在出队时才置位：同样是全 0 数组，第一层就会把 n - 1 个下标各入队多次，队列规模膨胀到 $O(n^2)$，时间和内存双爆。

忘记 i - 1 / i + 1 的越界检查：cur = 0 时访问 visited[-1]，Java 抛数组越界异常，Go 直接 panic；cur = n - 1 一侧同理。

把终点判断挪到入队处却不调整步数：走查用例 [100,-23,-23,404,100,23,23,23,3,404] 中，下标 9 是在 steps = 2 的那一层被入队的，入队即返回会得到 2，比正确答案 3 少一步。

每处理一个节点就让 steps 自增：steps 变成「已访问节点数」而非层数，同一个用例会返回 6 之类毫无意义的值。层计数必须锁定 size 后在层末自增。

当成从左往右的一维 DP 来推：arr = [7,6,9,6,9,6,9,7] 的正确答案是 1（下标 0 直接同值跳到下标 7），而按下标递推的写法既表达不了向右的远跳，也表达不了向左回退，会得到明显偏大的结果。

把同值跳跃理解成「只能跳到最近的同值下标」：走查用例里值 23 的下标组是 [5, 6, 7]，一步就能从 5 跳到 7；若限制成相邻同值，5 到 7 要两步，整条路径的步数被高估。

用 ArrayList 当队列并 remove(0)：每次出队都是 $O(n)$ 的元素搬移，n = 5 * 10^4 时退化成 $O(n^2)$。队列要用 ArrayDeque 或直接用下标游标扫切片。

预处理和 BFS 交织进行：边扩展边往哈希表里补下标，会导致展开某个值组时后面的同值下标还没入表，同值边被漏掉，最短路偏大。分组必须在 BFS 开始前一次性建完。

相似题目

题目	难度	考察点
127. 单词接龙	困难	节点是字符串，同样要靠通配符分桶预处理把 $O(n^2)$ 的两两比较降下来
815. 公交路线	困难	把「路线」而非「车站」当节点，与本题按值分组压边是同一种建图思路
1654. 到家的最少跳跃次数	中等	同为一维跳跃 BFS，但状态要附加「上一步是否后退」并自行推导搜索上界
1129. 颜色交替的最短路径	中等	状态是「节点 + 上一条边的颜色」，说明访问标记的维度不一定等于节点数
752. 打开转盘锁	中等	每个状态固定 8 个邻居，重点在死亡数字剪枝，适合演示双向 BFS
854. 相似度为 K 的字符串	困难	状态是排列，邻居靠交换生成，必须靠剪枝控制分支而不是靠压边
909. 蛇梯棋	中等	一维棋盘 BFS，邻居是 6 个骰子点数，还要处理编号到坐标的蛇形映射
542. 01 矩阵	中等	多源 BFS：把所有 0 一次性入队作为第 0 层，一遍扫出全部距离