原题链接:
https://leetcode.cn/problems/jump-game-iv/
这题基本思路比较BFS 每次扩展 i-1,i+1,值与arr[i]相同的点
但这题数据范围为5 * 10^4 如果arr[i]相等的边有m条 那么由于是一个无向图 那么这样的遍历的将会n^2 次 所以这一步是优化的关键
优化的思路是 是使用bfs 求最短路的路径 bfs求最短路只有第一次更新时求出的值是最小值 所以当你一次扩展值均为v的点后 直接删除v即可 下一次不必再遍历 即对于相同值得所有点只走一遍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        # 先记录所有与值相同点的下标
        h = defaultdict(list)
        for i, v in enumerate(arr):
            h[v].append(i)

        # 队列存 下标
        q = deque()
        q.append(0)
        n = len(arr)
        st = n * [inf]
        st[0] = 0
        while q:
            t = q.popleft()
            v = arr[t]

            for ne in t-1,t+1:
                if 0 <= ne < n and st[ne] > st[t] + 1:            
                    st[ne] = st[t] + 1
                    q.append(ne)
                if ne == n-1:
                    return st[ne]

            if not h[v]:
                continue

            for ne in h[v][::-1]:
                if st[ne] > st[t] + 1:
                    st[ne] = st[t] + 1
                    q.append(ne)
                if ne == n-1:
                    return st[ne]
				# 整个优化流程 最关键的一步 每这一步就会超时
                h[v] = None

        return st[n-1]