Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
一个树形结构的公司,所有人的id从0~n-1,老板的ID为headID,每个人有个直属上司manager[i](老板的上司-1),每个人需要informTime[i]去通知所有下属,问如果老板想要通知全公司,最快需要多少时间,DFS


 1 #1376
 2 #Runtime: 1174 ms (Beats 77.78%)
 3 #Memory: 51.1 MB (Beats 38.10%)
 4 
 5 class Solution(object):
 6     def numOfMinutes(self, n, headID, manager, informTime):
 7         """
 8         :type n: int
 9         :type headID: int
10         :type manager: List[int]
11         :type informTime: List[int]
12         :rtype: int
13         """
14         son = {}
15         for i in range(n):
16             if manager[i] >= 0:
17                 if manager[i] not in son:
18                     son[manager[i]] = [i]
19                 else:
20                     son[manager[i]].append(i)
21 
22         def DFS(id):
23             ans = 0
24             if id not in son:
25                 return 0
26             for i in son[id]:
27                 ans = max(DFS(i), ans)
28             return informTime[id] + ans
29                 
30         return DFS(headID)

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