Posted on 2022-12-05 12:51
Uriel 阅读(34)
评论(0) 编辑 收藏 引用 所属分类:
搜索 、
闲来无事重切Leet Code
给出一列数nums，在走到位置i时，可以跳到i-1或者i+1或者nums[i]值相同的任意位置，问最少几步可以跳到最后一个位置
用dict保存每一种数值出现在哪些位置，BFS+保存当前位置已经跳过了几步
然后直接暴力BFS会TLE，因为有可能出现nums的前9999个数相同，最后一个数不同的情况，这样每一次从q中取出一个数之后都要找一遍前9999个数（虽然因为都vis过，并不会压入队列），所以在用vis记录哪些位置已经访问过的同时，再用vis_group记录哪些数值已经被访问过，这样就不用每次在找一遍前9999个数寻找没有访问过的
1 #1345
2 #Runtime: 2380 ms
3 #Memory Usage: 32.8 MB
4
5 class Solution(object):
6 def minJumps(self, arr):
7 """
8 :type arr: List[int]
9 :rtype: int
10 """
11 arr_dict = {}
12 for i in range(len(arr)):
13 if arr[i] not in arr_dict:
14 arr_dict[arr[i]] = []
15 arr_dict[arr[i]].append(i)
16 q = deque([[0, 0]])
17 vis = set([0])
18 vis_group = set()
19 while q:
20 pos, step = q.popleft()
21 if pos == len(arr) - 1:
22 return step
23 if pos + 1 < len(arr) and pos + 1 not in vis:
24 vis.add(pos + 1)
25 q.append([pos + 1, step + 1])
26 if pos - 1 >= 0 and pos - 1 not in vis:
27 vis.add(pos - 1)
28 q.append([pos - 1, step + 1])
29 if arr[pos] not in vis_group:
30 for i in arr_dict[arr[pos]]:
31 if i not in vis:
32 vis.add(i)
33 q.append([i, step + 1])
34 vis_group.add(arr[pos])