Posted on 2022-12-05 12:51
Uriel 閱讀(43)
評論(0) 編輯 收藏 引用 所屬分類:
搜索 、
閑來無事重切Leet Code
給出一列數(shù)nums，在走到位置i時，可以跳到i-1或者i+1或者nums[i]值相同的任意位置，問最少幾步可以跳到最后一個位置
用dict保存每一種數(shù)值出現(xiàn)在哪些位置，BFS+保存當(dāng)前位置已經(jīng)跳過了幾步
然后直接暴力BFS會TLE，因為有可能出現(xiàn)nums的前9999個數(shù)相同，最后一個數(shù)不同的情況，這樣每一次從q中取出一個數(shù)之后都要找一遍前9999個數(shù)（雖然因為都vis過，并不會壓入隊列），所以在用vis記錄哪些位置已經(jīng)訪問過的同時，再用vis_group記錄哪些數(shù)值已經(jīng)被訪問過，這樣就不用每次在找一遍前9999個數(shù)尋找沒有訪問過的
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])