题目

N 个房间,开始时你位于 0 号房间。每个房间有不同的号码:0,1,2,...,N-1,并且房间里可能有一些钥匙能使你进入下一个房间。

在形式上,对于每个房间i 都有一个钥匙列表 rooms[i],每个钥匙 rooms[i][j][0,1,...,N-1] 中的一个整数表示,其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为v 的房间。

最初,除0 号房间外的其余所有房间都被锁住。

你可以自由地在房间之间来回走动。

如果能进入每个房间返回 true,否则返回 false

示例 1:

1
2
3
4
5
6
7
8
输入: [[1],[2],[3],[]]
输出: true
解释:
我们从 0 号房间开始,拿到钥匙 1。
之后我们去 1 号房间,拿到钥匙 2。
然后我们去 2 号房间,拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间,我们返回 true。

示例 2:

1
2
3
输入:[[1,3],[3,0,1],[2],[0]]
输出:false
解释:我们不能进入 2 号房间。

提示:

  1. 1 <= rooms.length <= 1000
  2. 0 <= rooms[i].length <= 1000
  3. 所有房间中的钥匙数量总计不超过 3000

题解

这道题仿佛是酒店老板的开房阴谋。想要开所有房间,我给他规划了两个方法。分别叫BFSDFS

BFS

BFS,即广度优先搜索

老板就问了:“我就是想开房,你能不能讲人话?”
说人话就是,我们按照这个步骤来做——

思路

  • 首先找到0号房间,把所有0号房间的钥匙都开一遍。
  • 进入刚刚开过的房间,再把它们房间里的钥匙再开一遍。
  • 重复以往,层层递进,直到找不到符合要求的节点。

思路很好理解对吧,就是一个从0号房间向外一层层扩散的过程。可是怎么实现呢?

实现

这里就要介绍一下队列,因为广度优先搜索队列是好基友。
什么是队列?就是一个先进先出的数组,和我们日常生活中的排队很像。当我们向队列插入一个新数的时候,它插在最后,当我们取出一个数的时候,要从头取。就像顾客开房,都是要排队的(假设没有VIP,不许杠!)。

补充——关于在Python中使用队列
Python 中,可以使用以下几种方法实现队列

  • collections包里的deque,对应操作
    • pop()从尾取出
    • appendleft() 从头插入
  • queue包中的queue,对应操作
    • put() 插入
    • get() 取出
  • 直接使用list,只要保证只使用
    • pop() 取出
    • insert(0,) 插入
      或者只使用
    • append() 插入
    • list[0]并且del list[0] 取出
      两者使用list方法的不同就区别于你把哪个当头,哪个当尾

三种方法各有优劣。

  • 第一种是正统的Python的双端队列,缺点是调用的函数有点复杂,可能一不小心写了append,就不对了。
  • 第二种使用封装的函数很直接,put()get()不容易搞混淆。但是queue类型其实里面本身就装了一个deque,有点脱裤子放X的感觉。
  • 第三种优势在于不用调包,但是函数使用逻辑可能造成混淆。在
    这里,完整版代码采用第二种,好理解,精简版代码采用第三种,省行数。三种方式可以按照你的喜好互相替换,完全不影响结果。

这时候老板又问了:“为什么广度优先搜索队列能勾搭到一块儿?这和排队有啥关系?”

我们可以这样利用队列实现广度优先搜索

  • 我们设置一个队列,先把初始房间添加进去
  • 规定每次从队列取出一个房间
  • 把这个房间的所有钥匙放到队列中。
  • 当这个队列为空的时候,说明遍历完成

进队列进去的是钥匙,出来的是房间,其实都是一回事,相当于出来的时候就开锁了。

因为队列每次取出的是最后的,而每次添加的是放在最前面,所以可以想象到,每次先处理的都是层级最少的,最接近初始点的,然后慢慢扩大,这样就实现了广度优先搜索

老板很好奇:“这个层级顺序有那么重要吗?咱也就是进去看看。”

在这道题目里,层级是不重要的,这也是为什么后来还有个深度优先搜索,也可以解决这道题目。但是广度优先搜索的特点就在于这个层级,在很多题目当中它是很重要的。有时候,对队列取出元素的时候,要设置循环,固定住当前的队列项,对当前的队列项操作——因为当前的队列项一定是相同层级的。例如,在我们寻找到达某个节点的最小步数的时候,层级也就是步数就显得尤为重要了。在leetcode当中,有很多题都是需要广度优先搜索的,这是一种解题的思想,要熟练掌握。而实现这个思想,又离不开队列。两者相辅相成。

老板“啪”地一下打我一拳:“净整这些有的没的,给我写!不然顾客都进来了!”

代码

1
2
3
4
5
6
7
8
9
10
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
visited, queue = {0}, [0]
while queue:
room_index = queue.pop()
for key in rooms[room_index]:
if key not in visited:
visited.add(key)
queue.insert(0,key)
return len(visited) == len(rooms)

DFS

DFS,即深度优先搜索

老板抢着说:“从你这小兔崽子的BFS里,我好想猜到了DFS是什么了,它是不是——”

思路

  • 先找第0个房间的第一个钥匙
  • 进入那个房间,再找它的第一个钥匙
  • 重复以往,直到没钥匙了,那么退回刚刚的房间
  • 找刚刚房间的第二把钥匙
  • 重复以往

思路很好理解对吧,就是一个从中间向一个房间深入的过程。可是怎么实现呢?

实现

还记得标题写的两个方法,三种实现吗?
这是因为 DFS 通常有两种实现方法,一种是递归,另一种是使用
这里就要介绍一下,因为深度优先搜索是好基友。
什么是栈?就是一个后进先出的数组,和我们日常生活中的插队很像。当我们向栈插入一个新数的时候,它插在最前面,当我们取出一个数的时候,要从头取。就像老板插队去开房,他不排队,直接插到第一个位置,下一个服务的就是他。

补充——关于在Python中使用栈
直接使用list即可,只使用它的这两个方法

  • pop()
  • append()

这时候老板又问了:“为什么广度优先搜索堆栈能勾搭到一块儿?东扯西扯的家伙。”

我们可以这样利用堆栈实现深度优先搜索

  • 我们设置一个栈,先把第一个房间添加进去
  • 规定每次从栈中取出一个钥匙
  • 找这个钥匙开的房间,并且把这个房间放到栈中。
  • 当这个栈为空的时候,说明遍历完成

因为栈每次取出的是最后的,而每次添加的也在最后,所以可以想象到,每次先处理的都是最深的,然后慢慢扩大,这样就实现了深度优先搜索

这时候老板很好奇:“这个深度顺序有那么重要吗?咱就是进去看看。”

在这道题目里,层级是不重要的,这也是为什么前面还有个广度优先搜索,也可以解决这道题目。在leetcode当中,有很多题都是需要深度优先搜索的,这是一种解题的思想,要熟练掌握。而实现这个思想,又离不开递归。两者相辅相成。

老板“啪”地一下打我一拳:“净整这些有的没的,给我写!不然顾客都进来了!”

代码一:使用栈

1
2
3
4
5
6
7
8
9
10
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
visited, stack = {0}, [0]
while stack:
room_index = stack.pop()
for key in rooms[room_index]:
if key not in visited:
visited.add(key)
stack.append(key)
return len(visited) == len(rooms)

代码二:使用递归

1
2
3
4
5
6
7
8
9
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
visited = {0}
def dfs(room_index,visited):
visited.add(room_index)
for key in rooms[room_index]:
if key not in visited: dfs(key,visited)
dfs(0,visited)
return len(visited) == len(rooms)