钥匙和房间

难度: Medium

有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。

当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。

给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入所有房间返回 true，否则返回 false。

示例 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 号房间。

提示：

n == rooms.length
2 <= n <= 1000
0 <= rooms[i].length <= 1000
1 <= sum(rooms[i].length) <= 3000
0 <= rooms[i][j] < n
所有 rooms[i] 的值 互不相同

Submission

运行时间: 23 ms

内存: 16.4 MB

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited=[False]*len(rooms)

        def bfs(index):
            q=collections.deque()
            q.append(index)
            visited[0]=True

            while len(q)!=0:
                index=q.popleft()
                for nextindex in rooms[index]:
                    if visited[nextindex]==False:
                        q.append(nextindex)
                        visited[nextindex]=True
        bfs(0)
        for  x in visited:
            if not x:
                return False
        return True

Explain

题解采用了广度优先搜索（BFS）的方法来遍历所有房间，检查是否能进入每个房间。首先，创建一个布尔列表visited来记录每个房间是否被访问过，初始化为False。BFS从房间0开始，将房间0标记为已访问。然后，使用队列来处理接下来的房间，队列中存储着待访问的房间。对于队列中的每个房间，检查该房间内的所有钥匙，如果该钥匙对应的房间未被访问，则将其加入队列，并标记为已访问。循环处理直到队列为空。最后，检查visited列表，如果所有房间都被访问过，则返回true，否则返回false。

时间复杂度: O(n + m)

空间复杂度: O(n)

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited = [False] * len(rooms)  # 标记房间是否已访问

        def bfs(index):
            q = collections.deque()  # 使用队列实现BFS
            q.append(index)
            visited[0] = True  # 标记房间0为已访问

            while q:
                index = q.popleft()  # 弹出队列的首元素
                for nextindex in rooms[index]:  # 遍历当前房间的所有钥匙
                    if not visited[nextindex]:  # 如果下一个房间未被访问
                        q.append(nextindex)  # 加入队列
                        visited[nextindex] = True  # 标记为已访问
        bfs(0)
        for x in visited:
            if not x:
                return False  # 存在未访问的房间
        return True  # 所有房间都已访问

Explore

BFS和DFS都可以用来解决这类问题，即遍历图中的所有节点。选择BFS而不是DFS的原因可能是因为BFS在这类问题中通常更直观，因为它按层次遍历节点，从一个房间出发，逐步探索所有可达的房间。BFS能较快地找到离起点近的节点，这在某些情况下可能更为高效。本质上，BFS是用队列实现的，逐层处理节点，而DFS是用栈实现的，它会深入到某一分支的最深处，然后再回溯。在这个特定的问题中，使用BFS或DFS并没有本质区别，因为最终目标是遍历所有节点，检查是否可以访问所有房间。

如果一个房间中有多把钥匙可以打开同一个房间，这将导致在队列中出现重复的房间编号，这可能会影响算法的效率，因为同一个房间会被多次加入队列并且其检查过程也会被多次执行。优化去重是有必要的，可以通过在将房间号加入队列之前检查该房间是否已被访问（即已经在队列中或已处理过）来实现。这样可以减少不必要的操作和内存使用，提高算法的效率。

在最坏的情况下，如果图是高度连接的，即每个房间都能直接或间接地到达其他所有房间，队列`q`可能会存储所有房间的编号，即在某一时刻，队列的大小可能等于房间总数。这种情况下，队列的大小将达到其最大值，即等于房间的总数。这将增大内存的使用，尤其是在房间数量非常多的情景下，可能对系统资源产生较大压力。

这段代码通过遍历`visited`列表来检查每个房间是否被访问过。如果发现有任何一个房间未被访问（即对应的`visited`值为`False`），则立即返回`False`。这种方式确保了只有当所有房间都被访问过时，函数才返回`True`。在这种实现中，没有明显的边界情况未被考虑。然而，如果输入的房间列表为空（即没有房间），根据实现，应当返回`True`，因为不存在未被访问的房间，这是一个需要确认具体业务逻辑是否接受的边界情况。