Posted on 2022-12-30 17:14
Uriel 閱讀(52)
評論(0) 編輯 收藏 引用 所屬分類:
搜索 、
閑來無事重切Leet Code
給出一幅有向無環圖（形式是給出graph: List[List[int]]，graph[i]記錄所有i指向的節點），輸出所有從0～n-1的路徑，簡單DFS or BFS
DFS：
1 #797
2 #Runtime: 78 ms (Beats 81.91%)
3 #Memory: 14.9 MB (Beats 45.48%)
4
5 class Solution(object):
6 def allPathsSourceTarget(self, graph):
7 """
8 :type graph: List[List[int]]
9 :rtype: List[List[int]]
10 """
11 ans = []
12 def DFS(node, p):
13 if node == len(graph) - 1:
14 ans.append(p)
15 return
16 for i in graph[node]:
17 DFS(i, p + [i])
18
19 DFS(0, [0])
20 return ans
BFS：
1 #797
2 #Runtime: 70 ms (Beats 94.47%)
3 #Memory: 14.8 MB (Beats 45.48%)
4
5 class Solution(object):
6 def allPathsSourceTarget(self, graph):
7 """
8 :type graph: List[List[int]]
9 :rtype: List[List[int]]
10 """
11 q = deque([[0]])
12 ans = []
13 while q:
14 p = q.popleft()
15 for i in graph[p[-1]]:
16 if i == len(graph) - 1:
17 ans.append(p + [i])
18 q.append(p + [i])
19 return ans