跳跃游戏 IV 图解题解

这道题到底在问什么

输入

arr=[100,-23,-23,404,100,23,23,23,3,404]

输出

3(0→4 同值跳,4→3 相邻,3→9 同值跳)

输入

arr=[7]

输出

0(已经在终点)

最优解：一步一步想明白

1. 3记住「值分组、分层 BFS、组用一次就清空」,下面逐帧套它。
2. 4先扫一遍数组,把相同值的下标归成组(右侧表)。比如值 100 在下标 [0,4],值 404 在 [3,9]——这两组就是后面「同值瞬移」的跳板。目标:从下标 0 走到下标 9(值 404)。
3. 5为什么同值跳厉害?像值 100 的 [0,4]:站在 0 可以一步直接跳到 4,跨过中间一大段。这就是本题能比逐格走快很多的原因。下面开始 BFS。
4. 6把起点下标 0(紫)标记已访问、放进队列,当前步数 0。开始一圈圈往外扩。
5. 7弹出下标 0(紫),值 100。先看同值组:把组里还没访问的下标 4(绿)入队,然后立刻清空值 100 这一组(右侧变「已清空」)——它们彼此一步可达,留着只会重复。
6. 8再看下标 0 的相邻 -1 和 1:把界内、没访问过的 1(绿)入队。另一个相邻 -1(越界),跳过。
7. 9这一圈所有下标都展开完了,往外推进一圈,步数 +1 = 1。下一圈要处理的是 [4, 1]。
8. 10弹出下标 4(紫),值 100 的同值组之前已经被清空了(右侧),没有新下标可跳,直接看相邻。
9. 11再看下标 4 的相邻 3 和 5:把界内、没访问过的 3、5(绿)入队。
10. 12弹出下标 1(紫),值 -23。先看同值组:把组里还没访问的下标 2(绿)入队,然后立刻清空值 -23 这一组(右侧变「已清空」)——它们彼此一步可达,留着只会重复。
11. 13再看下标 1 的相邻:0(已访问)、2(已访问),没有可入队的新下标。
12. 14这一圈所有下标都展开完了,往外推进一圈,步数 +1 = 2。下一圈要处理的是 [3, 5, 2]。
13. 15弹出下标 3(紫),值 404。先看同值组:把组里还没访问的下标 9(绿)入队,然后立刻清空值 404 这一组(右侧变「已清空」)——它们彼此一步可达,留着只会重复。
14. 16再看下标 3 的相邻:2(已访问)、4(已访问),没有可入队的新下标。
15. 17弹出下标 5(紫),值 23。先看同值组:把组里还没访问的下标 6、7(绿)入队,然后立刻清空值 23 这一组(右侧变「已清空」)——它们彼此一步可达,留着只会重复。
16. 18再看下标 5 的相邻:4(已访问)、6(已访问),没有可入队的新下标。
17. 19弹出下标 2(紫),值 -23 的同值组之前已经被清空了(右侧),没有新下标可跳,直接看相邻。
18. 20再看下标 2 的相邻:1(已访问)、3(已访问),没有可入队的新下标。
19. 21这一圈所有下标都展开完了,往外推进一圈,步数 +1 = 3。下一圈要处理的是 [9, 6, 7]。
20. 22弹出下标 9(绿),它正是最后一个下标 n−1 —— 第 3 圈碰到终点,答案就是 3 步。
21. 23回放这条最短路:下标 0 同值跳到 4(都是 100),4 相邻走到 3,3 同值跳到 9(都是 404),正好 3 步到终点。正因为同值组提供了「传送门」,才比一格格挪快得多。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
from collections import defaultdict, deque
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        pos = defaultdict(list)
        for i, x in enumerate(arr):
            pos[x].append(i)
        q = deque([0])
        seen = [False] * n
        seen[0] = True
        steps = 0
        while q:
            for _ in range(len(q)):
                i = q.popleft()
                if i == n - 1:
                    return steps
                for j in pos[arr[i]] + [i - 1, i + 1]:
                    if 0 <= j < n and not seen[j]:
                        seen[j] = True
                        q.append(j)
                pos[arr[i]].clear()
            steps += 1
        return -1

#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
    int minJumps(vector<int>& arr) {
        int n = arr.size();
        unordered_map<int, vector<int>> pos;
        for (int i = 0; i < n; ++i) pos[arr[i]].push_back(i);
        vector<int> seen(n);
        queue<int> q;
        q.push(0); seen[0] = 1;
        for (int steps = 0; !q.empty(); ++steps) {
            for (int sz = q.size(); sz--; ) {
                int i = q.front(); q.pop();
                if (i == n - 1) return steps;
                vector<int> next = pos[arr[i]];
                next.push_back(i - 1); next.push_back(i + 1);
                for (int j : next) if (j >= 0 && j < n && !seen[j]) {
                    seen[j] = 1; q.push(j);
                }
                pos[arr[i]].clear();
            }
        }
        return -1;
    }
};

import java.util.*;
class Solution {
    public int minJumps(int[] arr) {
        int n = arr.length;
        Map<Integer, List<Integer>> pos = new HashMap<>();
        for (int i = 0; i < n; i++) pos.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
        boolean[] seen = new boolean[n];
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(0); seen[0] = true;
        for (int steps = 0; !q.isEmpty(); steps++) {
            for (int sz = q.size(); sz > 0; sz--) {
                int i = q.poll();
                if (i == n - 1) return steps;
                List<Integer> next = pos.get(arr[i]);
                next.add(i - 1); next.add(i + 1);
                for (int j : next) if (j >= 0 && j < n && !seen[j]) {
                    seen[j] = true; q.offer(j);
                }
                next.clear();
            }
        }
        return -1;
    }
}

复杂度

面试官可能追问