§1

题目描述

给定数组 arr,从下标 0 出发,每步可走到相邻下标 i−1 / i+1,或任意满足 arr[j]==arr[i] 的下标 j。返回到达最后一个下标 n−1 的最少步数。

输入 = arr=[100,-23,-23,404,100,23,23,23,3,404]　输出 = 3(0→4 同值跳,4→3 相邻,3→9 同值跳)

输入 = arr=[7]　输出 = 0(已经在终点)

§2

思路解析动画文字版

记住「值分组、分层 BFS、组用一次就清空」,下面逐帧套它。

先扫一遍数组,把相同值的下标归成组(右侧表)。比如值 100 在下标 [0,4],值 404 在 [3,9]——这两组就是后面「同值瞬移」的跳板。目标:从下标 0 走到下标 9(值 404)。

为什么同值跳厉害?像值 100 的 [0,4]:站在 0 可以一步直接跳到 4,跨过中间一大段。这就是本题能比逐格走快很多的原因。下面开始 BFS。

把起点下标 0(紫)标记已访问、放进队列,当前步数 0。开始一圈圈往外扩。

弹出下标 0(紫),值 100。先看同值组:把组里还没访问的下标 4(绿)入队,然后立刻清空值 100 这一组(右侧变「已清空」)——它们彼此一步可达,留着只会重复。

再看下标 0 的相邻 -1 和 1:把界内、没访问过的 1(绿)入队。另一个相邻 -1(越界),跳过。

这一圈所有下标都展开完了,往外推进一圈,步数 +1 = 1。下一圈要处理的是 [4, 1]。

弹出下标 4(紫),值 100 的同值组之前已经被清空了(右侧),没有新下标可跳,直接看相邻。

再看下标 4 的相邻 3 和 5:把界内、没访问过的 3、5(绿)入队。

弹出下标 1(紫),值 -23。先看同值组:把组里还没访问的下标 2(绿)入队,然后立刻清空值 -23 这一组(右侧变「已清空」)——它们彼此一步可达,留着只会重复。

再看下标 1 的相邻:0(已访问)、2(已访问),没有可入队的新下标。

这一圈所有下标都展开完了,往外推进一圈,步数 +1 = 2。下一圈要处理的是 [3, 5, 2]。

弹出下标 3(紫),值 404。先看同值组:把组里还没访问的下标 9(绿)入队,然后立刻清空值 404 这一组(右侧变「已清空」)——它们彼此一步可达,留着只会重复。

再看下标 3 的相邻:2(已访问)、4(已访问),没有可入队的新下标。

弹出下标 5(紫),值 23。先看同值组:把组里还没访问的下标 6、7(绿)入队,然后立刻清空值 23 这一组(右侧变「已清空」)——它们彼此一步可达,留着只会重复。

再看下标 5 的相邻:4(已访问)、6(已访问),没有可入队的新下标。

弹出下标 2(紫),值 -23 的同值组之前已经被清空了(右侧),没有新下标可跳,直接看相邻。

再看下标 2 的相邻:1(已访问)、3(已访问),没有可入队的新下标。

这一圈所有下标都展开完了,往外推进一圈,步数 +1 = 3。下一圈要处理的是 [9, 6, 7]。

弹出下标 9(绿),它正是最后一个下标 n−1 —— 第 3 圈碰到终点,答案就是 3 步。

回放这条最短路:下标 0 同值跳到 4(都是 100),4 相邻走到 3,3 同值跳到 9(都是 404),正好 3 步到终点。正因为同值组提供了「传送门」,才比一格格挪快得多。

边界:单元素 0 步;首尾同值 1 步;全不同值就逐格走。

两个延伸:可上双向 BFS 提速;换邻居规则时当心边数爆炸。

§3

参考代码

from typing import Listfrom collections import defaultdict, dequeclass 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

看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。

§4

复杂度

时间：O(n)，每个下标入队一次;每个值的组只被展开一次(用后清空),所有同值边总共只走 O(n) 次
空间：O(n)，值→下标表、seen 数组、队列都是 O(n)

§5

易错点

✗ 错误写法：同值组用完不清空

✓ 正确写法：展开一个下标后清空它所在值的组

一个值若有 m 个下标,不清空会让这 m 个下标两两互相展开,退化成 O(n²) 甚至超时

✗ 错误写法：改用 DFS 或贪心,一头扎进同值跳就往下走

✓ 正确写法：用 BFS 按距离扩散(分层、或给每个点记 dist 都对)

DFS/贪心不保证先到终点的就是最短;只要按距离一圈圈扩散——无论分层计数还是给每点记 dist——首次到终点即最短

✗ 错误写法：忘了相邻的 i−1 / i+1 也是合法移动

✓ 正确写法：邻居 = 同值组 + 左右相邻

只考虑同值跳会漏掉普通走步,可能到不了或多算

面试追问把动画讲成自己的话

追问能不能用双向 BFS 进一步加速?

可以。从起点和终点同时向中间扩展,两边相遇时把各自步数相加即为答案。双向 BFS 在「分支因子大、最短路较长」时能把搜索空间从指数级近似开方,本题同值组让分支因子可能很大,双向 BFS 常有明显常数级甚至数量级加速。实现上要交替扩展较小的一侧、注意相遇判定。

追问如果还允许「跳到 arr[j] = arr[i] + k」这类更复杂的边呢?

思路不变,仍是无权图最短路用 BFS;区别只是「邻居怎么生成」。把生成邻居的规则换掉即可,但要小心新规则会不会让边数爆炸——必要时同样用「分组、用后清理」之类的手段控制同类边只展开一次。

这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。

把这道题真正学会，再走

图解算法年卡 ¥99 /年

✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
✓学习报告，记录每道题的掌握程度

599道动画图解

28课数据结构

¥0.27折合 / 天

76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解

¥99 开通年卡 →

想成体系刷透这类套路？去图解算法专题

from typing import Listfrom collections import defaultdict, dequeclass 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

跳跃游戏 IV

题目描述

思路解析动画文字版

参考代码

复杂度

易错点

面试追问把动画讲成自己的话

把这道题真正学会，再走

跳跃游戏 IV

题目描述

思路解析动画文字版

参考代码

复杂度

易错点

面试追问把动画讲成自己的话

把这道题真正学会，再走