LeetCode 1345. 跳跃游戏 IV

约 6 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 困难 未解决 2-5 字节 华为
标签
数组 哈希表 广度优先搜索

题目描述

✅ 1345. 跳跃游戏 IV

image-20260928224306959

image-20260928224306960

题意分析

从下标 0 出发，每步可以移到合法的左右相邻下标，或跳到任意另一个值相同的下标，求到达末尾的最少跳数。每次跳跃都算一步，跳得远并不增加代价。

解法：BFS + 同值下标分组

核心思路

[!blue]

把每个数组下标看作图节点，所有允许的跳跃都是代价为 1 的边。BFS 按距离逐层扩展，处理距离为 steps 的节点时，新发现的邻居距离就是 steps + 1，因此第一次处理到末尾时即可返回当前层数。

左右邻居可以直接计算，同值邻居则预先用 indices[value] 保存全部下标。一个值出现 $t$ 次时，每个位置都能跳到同组其他位置，如果反复扫描整组就会产生 $O(t^2)$ 的工作量。

设某个值组第一次被展开时，当前节点的最短距离为 $d$。这次扫描后，组内每个节点都已以不超过 $d+1$ 的距离被发现。BFS 之后处理的同组节点距离不会小于 $d$，再从它跳到组内成员，也不可能得到比已有距离更短的结果。因此整组扫描一次后就能删除；这些节点自己的左右邻居仍会在各自出队时正常扩展。

visited 在入队时就置为真，让左右移动和同值跳跃统一判重，保证每个下标只入队一次。每层开始固定当前队列长度 size，只处理这批节点，期间追加的节点属于下一层；全部处理完后才增加 steps。

解题步骤

  • 预先建立完整值到下标列表。
  • 按层扩展左右邻居与同值组，发现即标记。
  • 同值组扫描后删除。
  • 处理到末下标返回层数。

数组只有一个元素时，起点就是终点，直接返回 0。题目保证数组非空，而且一直向右移动总能到达末尾，因此正常输入一定会找到答案。

代码实现

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);
                    }

                    // 该值组已全部发现，删除后避免再次扫描整组。
                    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)
            }

            // 该值组已全部发现，删除后避免再次扫描整组。
            delete(indices, arr[cur])
        }
        queue = queue[size:]
        steps++
    }

    return -1
}

复杂度分析

  • 时间复杂度：期望 $O(n)$。每个下标最多入队一次，左右邻居各检查一次；所有同值列表总长度为 $n$，且每组只扫描一次。哈希表操作按平均常数时间计算。
  • 空间复杂度：$O(n)$，分组、访问与队列。

关键点总结

[!green]

  • 节点访问标记与值组是否展开是两类状态。
  • 同值跳跃可跨到任一同值位置，不局限最近者。
  • Go 代码在一层结束后执行 queue = queue[size:]，留下的正是本轮追加的下一层节点。

易错点总结

[!yellow]

  • 重复扫描同值列表，会在大量重复值时退化为平方工作量。
  • 只保留向右移动，会漏掉先远跳再左移的最优路径。
  • 每出队一个节点就增加步数，会把节点数量当距离。

相似题目

题目 难度 关联与区别
815. 公交路线 困难 同样通过共享属性形成大量隐式连接，某个同值组或公交线路展开一次后应避免重复扫描。
1306. 跳跃游戏 III 中等 同样在数组下标图上BFS，本题额外允许跳到任意同值位置，边的生成方式不同。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/74622424
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！