Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一幅有向无环图(形式是给出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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理