Posted on 2022-12-20 14:48
Uriel 阅读(29)
评论(0) 编辑 收藏 引用 所属分类:
搜索 、
闲来无事重切Leet Code
给出每个房间内拥有的钥匙（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)