Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出每个房间内拥有的钥匙(room[i], 一个list),每个钥匙的数值j表示可以开第j个房间,房间0没有上锁,问是否有办法进入所有房间,简单DFS或BFS
速度一般,目前没想到优化

DFS版

 1 #841
 2 #Runtime: 311 ms (Beats 5.61%)
 3 #Memory: 42.3 MB (Beats 5.96%)
 4 
 5 class Solution(object):
 6     def canVisitAllRooms(self, rooms):
 7         """
 8         :type rooms: List[List[int]]
 9         :rtype: bool
10         """
11         def DFS(vis, cnt, keys):
12             if cnt == len(rooms):
13                 return True
14             for i in keys:
15                  if i not in vis:
16                      vis.add(i)
17                      keys = keys.union(set(rooms[i])) 
18                      if DFS(vis, cnt + 1, keys):
19                          return True
20             return False
21         return DFS(set([0]), 1, set(rooms[0]))

BFS版

 1 #841
 2 #Runtime: 119 ms (Beats 16.14%)
 3 #Memory: 14.4 MB (Beats 9.12%)
 4 
 5 class Solution(object):
 6     def canVisitAllRooms(self, rooms):
 7         """
 8         :type rooms: List[List[int]]
 9         :rtype: bool
10         """
11         q = deque([set(rooms[0])])
12         print(q)
13         vis = set([0])
14         while q:
15             keys = q.popleft()
16             for i in keys:
17                 if i not in vis:
18                     vis.add(i)
19                     keys = keys.union(rooms[i])
20                     q.append(keys)
21         return len(vis) == len(rooms)


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