• 力扣第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

    1. class Solution {
    2. public:
    3.     // 深度优先搜索函数，用于访问房间和相关钥匙
    4.     void dfs(vectorint>> &rooms, int key, vector<bool> &visited) {
    5.         // 如果当前钥匙已经被访问过，则直接返回
    6.         if (visited[key]) {
    7.             return;
    8.         }
    9.         visited[key] = true; // 标记当前钥匙为已访问
    10.         vector<int> keys = rooms[key]; // 获取当前房间中的钥匙
    11.         for (int nextKey : keys) {
    12.             dfs(rooms, nextKey, visited); // 对每把钥匙进行深度优先搜索
    13.         }
    14.     }
    15.  
    16.     // 判断是否能访问所有房间
    17.     bool canVisitAllRooms(vectorint>>& rooms) {
    18.         vector<bool> visited(rooms.size(), false); // 初始化访问状态数组
    19.         dfs(rooms, 0, visited); // 从第一个房间开始进行深度优先搜索
    20.         // 检查是否所有房间都被访问过
    21.         for (bool visit : visited) {
    22.             if (!visit) {
    23.                 return false; // 如果有任意一个房间未被访问，则返回false
    24.             }
    25.         }
    26.         return true; // 所有房间都被访问过，返回true
    27.     }
    28. };

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

    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

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

    Java双代码

    DFS

    1. class Solution {
    2.     // 使用深度优先搜索来访问房间
    3.     private void dfs(int key, List> rooms, List visited) {
    4.         // 如果当前房间已经访问过，则直接返回
    5.         if (visited.get(key)) {
    6.             return;
    7.         }
    8.         // 将当前房间标记为已访问
    9.         visited.set(key, true);
    10.         // 遍历当前房间中的钥匙，继续深度优先搜索
    11.         for (int k : rooms.get(key)) {
    12.             dfs(k, rooms, visited);
    13.         }
    14.     }
    15.  
    16.     // 判断是否可以访问所有房间
    17.     public boolean canVisitAllRooms(List> rooms) {
    18.         // 初始化一个列表来记录每个房间是否被访问过
    19.         List visited = new ArrayList(){{
    20.             // 初始化为 false，表示所有房间都未被访问过
    21.             for(int i = 0 ; i < rooms.size(); i++){
    22.                 add(false);
    23.             }
    24.         }};
    25.         // 从 0 号房间开始深度优先搜索
    26.         dfs(0, rooms, visited);
    27.         // 检查是否所有房间都被访问过
    28.         for (boolean flag : visited) {
    29.             if (!flag) {
    30.                 return false; // 如果有任意一个房间未被访问，则返回 false
    31.             }
    32.         }
    33.         return true; // 否则返回 true，表示所有房间都被成功访问了
    34.     }
    35. }

    BFS

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

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

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

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

  • 相关阅读:
    strimzi实战之一：简介和准备
    torch.nn.DataParallel类
    姓氏起源查询易语言代码
    【Android安全】Android SELinux机制 | Android 访问控制模型
    关于“兆易创新杯”中国研究生电子设计竞赛的一点个人小经验
    如何测试响应式网站
    ESP32-MicroPython 开发环境
    redis大全
    网络安全笔记-加解密算法
    148-153-Hadoop-调优-多目录-黑白名单
  • 原文地址：https://blog.csdn.net/jgk666666/article/details/134368694