Posted on 2022-12-30 17:14
Uriel 阅读(49)
评论(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