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