Leetcode刷题（18）栈的应用：钥匙和房间 (深度分析堆栈使用的易

visited.add(0) # 0号房间探索过
my_stack.append(0) # 0号房间的钥匙需要遍历

while my_stack:
cur = my_stack.pop()
for k in rooms[cur]: # 钥匙列表
if k not in visited:
visited.add(k) # 说明可以进入新的房间
my_stack.append(k) # 新的房间有新的钥匙

return len(visited) == len(rooms)

2.1 运行结果：

2.2 分析：

快了40ms, 显著的速度提升！

此处我用的是栈，因此属于深度优先搜索；如果这道题，我把栈换成队列，就变成广度优先搜索，然而，对于这道题来说，这两种方法并没有什么差别。因为这而的主体是每进入一个房间，判断里面的钥匙是否用过，然后没用过的，加入待探索的表，而待探索的表要以什么顺序去找，是无所谓的。

作者：吕诺

 3/3   首页 上一页 1 2 3