力扣第841题 钥匙和房间 C++ DFS BFS 附Java代码

题目

841. 钥匙和房间

中等

相关标签

深度优先搜索   广度优先搜索  图

有 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] 的值 互不相同

思路和解题方法  深度优先搜索 

1. 首先是 dfs 函数：

   • 这个函数使用深度优先搜索（DFS）来模拟访问房间和获取钥匙的过程。
   • 它接受三个参数：rooms 代表房间及其对应的钥匙信息的二维数组，key 代表当前要访问的房间号，visited 代表记录房间访问状态的布尔数组。
   • 函数首先检查当前房间是否已经访问过，如果是，则直接返回，避免重复访问；否则将当前房间标记为已访问，并获取当前房间中的钥匙信息。
   • 然后对每把钥匙都进行深度优先搜索，即递归调用 dfs 函数，以访问新房间并获取新房间中的钥匙。

2. 接下来是 canVisitAllRooms 函数：

   • 这个函数判断是否可以访问所有房间。
   • 首先初始化了一个布尔数组 visited，用于记录各个房间的访问状态，初始值为 false 表示未访问。
   • 然后调用了 dfs 函数，从第一个房间开始进行深度优先搜索，以尝试访问所有可以到达的房间。
   • 最后遍历 visited 数组，如果有任意一个房间未被访问，则返回 false，表示无法访问所有房间；否则返回 true，表示可以成功访问所有房间。

复杂度

        时间复杂度:

                O(n+k)

时间复杂度取决于房间数量和钥匙数量，假设有 n 个房间和 k 个钥匙。在最坏情况下，每个房间都需要被访问一次，并且每个钥匙都需要被尝试使用一次。因此，时间复杂度为 O(n+k)。

        空间复杂度

                O(n)

至于空间复杂度，主要是由递归调用的深度决定的，最坏情况下可能需要 O(n) 的栈空间。此外，还需使用一个大小为 n 的布尔数组来记录各个房间的访问状态，因此整体空间复杂度为 O(n)。

c++ 代码  1

class Solution {
public:// 深度优先搜索函数，用于访问房间和相关钥匙void dfs(vector<vector<int>> &rooms, int key, vector<bool> &visited) {// 如果当前钥匙已经被访问过，则直接返回if (visited[key]) {return;}visited[key] = true; // 标记当前钥匙为已访问vector<int> keys = rooms[key]; // 获取当前房间中的钥匙for (int nextKey : keys) {dfs(rooms, nextKey, visited); // 对每把钥匙进行深度优先搜索}}// 判断是否能访问所有房间bool canVisitAllRooms(vector<vector<int>>& rooms) {vector<bool> visited(rooms.size(), false); // 初始化访问状态数组dfs(rooms, 0, visited); // 从第一个房间开始进行深度优先搜索// 检查是否所有房间都被访问过for (bool visit : visited) {if (!visit) {return false; // 如果有任意一个房间未被访问，则返回false}}return true; // 所有房间都被访问过，返回true}
};

思路和解题方法  广度优先搜索 

1. 首先是 dfs 函数：

   • 这个函数使用深度优先搜索（DFS）来模拟访问房间和获取钥匙的过程。
   • 它接受三个参数：rooms 代表房间及其对应的钥匙信息的二维数组，key 代表当前要访问的房间号，visited 代表记录房间访问状态的布尔数组。
   • 函数首先检查当前房间是否已经访问过，如果是，则直接返回，避免重复访问；否则将当前房间标记为已访问，并获取当前房间中的钥匙信息。
   • 然后对每把钥匙都进行深度优先搜索，即递归调用 dfs 函数，以访问新房间并获取新房间中的钥匙。

2. 接下来是 canVisitAllRooms 函数：

   • 这个函数判断是否可以访问所有房间。
   • 首先初始化了一个布尔数组 visited，用于记录各个房间的访问状态，初始值为 false 表示未访问。
   • 然后调用了 dfs 函数，从第一个房间开始进行深度优先搜索，以尝试访问所有可以到达的房间。
   • 最后遍历 visited 数组，如果有任意一个房间未被访问，则返回 false，表示无法访问所有房间；否则返回 true，表示可以成功访问所有房间。

复杂度

        时间复杂度:

                O(n^2)

时间复杂度分析：

• 在最坏情况下，每个房间都需要被访问一次，因此广度优先搜索的时间复杂度为 O(n)，其中 n 为房间的数量。
• 对于每个房间，我们需要遍历其对应的钥匙列表，这一步的时间复杂度也是 O(n)，因为在最坏情况下，每个房间都有 n 个钥匙。
• 因此总体时间复杂度为 O(n^2)。

        空间复杂度

                O(n)

空间复杂度分析：

• visited 数组占用了 O(n) 的额外空间，用于标记每个房间是否被访问过。
• 队列 que 最大可能包含 n 个元素，因此队列的空间复杂度也是 O(n)。
• 因此总体空间复杂度为 O(n)。

c++ 代码  2

class Solution {bool bfs(const vector<vector<int>>& rooms) {vector<int> visited(rooms.size(), 0); // 用于标记房间是否被访问过，初始值都为 0visited[0] = 1; // 从 0 号房间开始访问，将 0 号房间标记为已访问queue<int> que;que.push(0); // 将 0 号房间加入队列，表示从这里开始访问// 广度优先搜索的过程while (!que.empty()) {int key = que.front(); que.pop(); // 取出队列中的下一个要访问的房间号vector<int> keys = rooms[key]; // 获取当前房间中的钥匙信息for (int nextKey : keys) { // 遍历当前房间的钥匙，尝试打开新的房间if (!visited[nextKey]) { // 如果遇到未访问过的房间que.push(nextKey); // 将该房间加入队列，表示要访问这个房间visited[nextKey] = 1; // 并标记该房间为已访问}}}// 检查房间是不是都遍历过了for (int i : visited) {if (i == 0) return false; // 如果有任意一个房间未被访问，则返回 false}return true; // 否则返回 true，表示所有房间都被成功访问了}public:bool canVisitAllRooms(vector<vector<int>>& rooms) {return bfs(rooms); // 调用 bfs 函数进行广度优先搜索，判断是否可以访问所有房间}
};

Java双代码

DFS

class Solution {// 使用深度优先搜索来访问房间private void dfs(int key, List<List<Integer>> rooms, List<Boolean> visited) {// 如果当前房间已经访问过，则直接返回if (visited.get(key)) {return;}// 将当前房间标记为已访问visited.set(key, true);// 遍历当前房间中的钥匙，继续深度优先搜索for (int k : rooms.get(key)) {dfs(k, rooms, visited);}}// 判断是否可以访问所有房间public boolean canVisitAllRooms(List<List<Integer>> rooms) {// 初始化一个列表来记录每个房间是否被访问过List<Boolean> visited = new ArrayList<Boolean>(){{// 初始化为 false，表示所有房间都未被访问过for(int i = 0 ; i < rooms.size(); i++){add(false);}}};// 从 0 号房间开始深度优先搜索dfs(0, rooms, visited);// 检查是否所有房间都被访问过for (boolean flag : visited) {if (!flag) {return false; // 如果有任意一个房间未被访问，则返回 false}}return true; // 否则返回 true，表示所有房间都被成功访问了}
}

BFS

class Solution {public boolean canVisitAllRooms(List<List<Integer>> rooms) {boolean[] visited = new boolean[rooms.size()]; // 用一个 boolean 数组记录房间是否被访问visited[0] = true; // 标记第 0 个房间为已访问Queue<Integer> queue = new ArrayDeque<>(); // 创建一个队列用于广度优先搜索queue.add(0); // 将第 0 个房间加入队列，表示从该房间开始访问其他房间while (!queue.isEmpty()) {int curKey = queue.poll(); // 取出队首房间// 遍历当前房间中的钥匙，标记并加入队列for (int key : rooms.get(curKey)) {if (visited[key]) continue; // 如果房间已经访问过，则继续下一次循环visited[key] = true; // 标记该房间为已访问queue.add(key); // 将该房间加入队列，表示将从该房间开始继续访问其他房间}}// 检查是否所有房间都被访问过for (boolean key : visited) {if (!key) {return false; // 如果有任意一个房间未被访问，则返回 false}}return true; // 否则返回 true，表示所有房间都被成功访问了}
}

觉得有用的话可以点点赞，支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦  >人<  。