跳至主要內容

0841. 钥匙和房间

ITCharge大约 2 分钟

0841. 钥匙和房间open in new window

  • 标签:深度优先搜索、广度优先搜索、图
  • 难度:中等

题目链接

题目大意

描述:有 n 个房间,编号为 0 ~ n - 1,每个房间都有若干把钥匙,每把钥匙上都有一个编号,可以开启对应房间号的门。最初,除了 0 号房间外其他房间的门都是锁着的。

现在给定一个二维数组 roomsrooms[i][j] 表示第 i 个房间的第 j 把钥匙所能开启的房间号。

要求:判断是否能开启所有房间的门。如果能开启,则返回 True。否则返回 False

说明

  • n==rooms.lengthn == rooms.length
  • 2n10002 \le n \le 1000
  • 0rooms[i].length10000 \le rooms[i].length \le 1000
  • 1sum(rooms[i].length)30001 \le sum(rooms[i].length) \le 3000
  • 0rooms[i][j]<n0 \le rooms[i][j] < n
  • 所有 rooms[i]rooms[i] 的值互不相同。

示例

  • 示例 1:
输入:rooms = [[1],[2],[3],[]]
输出:True
解释:
我们从 0 号房间开始,拿到钥匙 1。
之后我们去 1 号房间,拿到钥匙 2。
然后我们去 2 号房间,拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间,我们返回 true。
  • 示例 2:
输入:rooms = [[1,3],[3,0,1],[2],[0]]
输出:False
解释:我们不能进入 2 号房间。

解题思路

思路 1:深度优先搜索

x 号房间有 y 号房间的钥匙时,就可以认为我们可以通过 x 号房间去往 y 号房间。现在把 n 个房间看做是拥有 n 个节点的图,则上述关系可以看做是 xy 点之间有一条有向边。

那么问题就变为了给定一张有向图,从 0 节点开始出发,问是否能到达所有的节点。

我们可以使用深度优先搜索的方式来解决这道题,具体做法如下:

  1. 使用 set 集合变量 visited 来统计遍历到的节点个数。
  2. 0 节点开始,使用深度优先搜索的方式遍历整个图。
  3. 将当前节点 x 加入到集合 visited 中,遍历当前节点的邻接点。
    1. 如果邻接点不再集合 visited 中,则继续递归遍历。
  4. 最后深度优先搜索完毕,判断一下遍历到的节点个数是否等于图的节点个数(即集合 visited 中的元素个数是否等于节点个数)。
    1. 如果等于,则返回 True
    2. 如果不等于,则返回 False

思路 1:代码

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        def dfs(x):
            visited.add(x)
            for key in rooms[x]:
                if key not in visited:
                    dfs(key)
        visited = set()
        dfs(0)
        return len(visited) == len(rooms)

思路 1:复杂度分析

  • 时间复杂度O(n+m)O(n + m),其中 nn 是房间的数量,mm 是所有房间中的钥匙数量的总数。
  • 空间复杂度O(n)O(n),递归调用的栈空间深度不超过 nn