Update 0841. 钥匙和房间.md

itcharge · itcharge · commit 5325cb796121 · 2022-09-05T16:11:11.000+08:00
diff --git a/Solutions/0841. 钥匙和房间.md b/Solutions/0841. 钥匙和房间.md
@@ -5,23 +5,58 @@
 
 ## 题目大意
 
-有 `n` 个房间，编号为 `0` ~ `n - 1`，每个房间都有若干把钥匙，每把钥匙上都有一个编号，可以开启对应房间号的门。最初，除了 `0` 号房间外其他房间的门都是锁着的。
+**描述**：有 `n` 个房间，编号为 `0` ~ `n - 1`，每个房间都有若干把钥匙，每把钥匙上都有一个编号，可以开启对应房间号的门。最初，除了 `0` 号房间外其他房间的门都是锁着的。
 
-现在给定一个二维数组 `rooms`，`rooms[i][j]` 表示第 i 个房间的第 j 把钥匙所能开启的房间号。
+现在给定一个二维数组 `rooms`，`rooms[i][j]` 表示第 `i` 个房间的第 `j` 把钥匙所能开启的房间号。
 
-要求：判断是否能开启所有房间的门。如果能开启，则返回 `True`。否则返回 `False`。
+**要求**：判断是否能开启所有房间的门。如果能开启，则返回 `True`。否则返回 `False`。
+
+**说明**：
+
+- $n == rooms.length$。
+- $2 \le n \le 1000$。
+- $0 \le rooms[i].length \le 1000$。
+- $1 \le sum(rooms[i].length) \le 3000$。
+- $0 \le rooms[i][j] < n$。
+- 所有 $rooms[i]$ 的值互不相同。
+
+**示例**：
+
+```Python
+输入：rooms = [[1],[2],[3],[]]
+输出：True
+解释：
+我们从 0 号房间开始，拿到钥匙 1。
+之后我们去 1 号房间，拿到钥匙 2。
+然后我们去 2 号房间，拿到钥匙 3。
+最后我们去了 3 号房间。
+由于我们能够进入每个房间，我们返回 true。
+
+
+输入：rooms = [[1,3],[3,0,1],[2],[0]]
+输出：False
+解释：我们不能进入 2 号房间。
+```
 
 ## 解题思路
 
+### 思路 1：深度优先搜索
+
 当 `x` 号房间有 `y` 号房间的钥匙时，就可以认为我们可以通过 `x` 号房间去往 `y` 号房间。现在把 `n` 个房间看做是拥有 `n` 个节点的图，则上述关系可以看做是 `x` 与 `y` 点之间有一条有向边。
 
 那么问题就变为了给定一张有向图，从 `0` 节点开始出发，问是否能到达所有的节点。
 
-我们可以先建图，然后可以从 `0` 节点开始，使用深度优先搜索的方式遍历整个图，并使用 `set` 集合来统计遍历到的节点个数。
+我们可以使用深度优先搜索的方式来解决这道题，具体做法如下：
 
-最终判断一下遍历到的节点个数是否等于图的节点个数。如果等于，则返回 `True`，否则返回 `False`。
+1. 使用 set 集合变量 `visited` 来统计遍历到的节点个数。
+2. 从 `0` 节点开始，使用深度优先搜索的方式遍历整个图。
+3. 将当前节点 `x` 加入到集合 `visited` 中，遍历当前节点的邻接点。
+   1. 如果邻接点不再集合 `visited` 中，则继续递归遍历。
+4. 最后深度优先搜索完毕，判断一下遍历到的节点个数是否等于图的节点个数（即集合 `visited` 中的元素个数是否等于节点个数）。
+   1. 如果等于，则返回 `True`
+   2. 如果不等于，则返回 `False`。
 
-## 代码
+### 思路 1：代码
 
 ```Python
 class Solution:
@@ -36,3 +71,7 @@ class Solution:
         return len(visited) == len(rooms)
 ```
 
+### 思路 1：复杂度分析
+
+- **时间复杂度**：$O(n + m)$，其中 $n$ 是房间的数量，$m$ 是所有房间中的钥匙数量的总数。
+- **空间复杂度**：$O(n)$，递归调用的栈空间深度不超过 $n$。
