(图论) 841. 钥匙和房间 ——【Leetcode每日一题】

news/2024/2/28 9:44:18

❓ 841. 钥匙和房间

难度:中等

n 个房间,房间按从 0n - 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 = = r o o m s . l e n g t h n == rooms.length n==rooms.length
  • 2 < = n < = 1000 2 <= n <= 1000 2<=n<=1000
  • 0 < = r o o m s [ i ] . l e n g t h < = 1000 0 <= rooms[i].length <= 1000 0<=rooms[i].length<=1000
  • 1 < = s u m ( r o o m s [ i ] . l e n g t h ) < = 3000 1 <= sum(rooms[i].length) <= 3000 1<=sum(rooms[i].length)<=3000
  • 0 < = r o o m s [ i ] [ j ] < n 0 <= rooms[i][j] < n 0<=rooms[i][j]<n
    所有 r o o m s [ i ] rooms[i] rooms[i] 的值 互不相同

💡思路:

可以将每个房间当作图中的结点,钥匙当作图中的边,只要所有结点能够连通,则返回true;

法一:BFS

数组 rooms 的长度即为 房间的总个数:(bfs)

  • 可以设置一个数组 open,记录是否找到钥匙;
  • 以及一个队列 keys,存储在每个房间取得的钥匙;
  • 再另设一个变量 count 记录已打开房间的个数,最后只需比较 count 是否等于房间的总个数。

法二:DFS

我们可以使用深度优先搜索的方式遍历整张图,

统计可以到达的节点个数,并利用数组 open 标记当前节点是否访问过,以防止重复访问。

🍁代码:(C++、Java)

法一:BFS
C++

class Solution {
public:bool canVisitAllRooms(vector<vector<int>>& rooms) {queue<int> keys;vector<int> open(rooms.size());open[0] = 1;int count = 1;for(int k : rooms[0]){keys.push(k);}while(!keys.empty()){int key = keys.front();keys.pop();if(open[key] == 0){for(int k : rooms[key]){keys.push(k);}open[key] = 1;count++;}}return count == rooms.size();}
};

Java

class Solution {public boolean canVisitAllRooms(List<List<Integer>> rooms) {Queue<Integer> keys = new LinkedList();int[] open = new int[rooms.size()];open[0] = 1;int count = 1;for(int k : rooms.get(0)){keys.offer(k);}while(!keys.isEmpty()){int key = keys.poll();if(open[key] == 0){for(int k : rooms.get(key)){keys.offer(k);}open[key] = 1;count++;}}return count == rooms.size();}
}

法二:DFS
C++

class Solution {
private:void dfs(const vector<vector<int>>& rooms, int key, vector<int>& open){if(open[key] == 1) return;open[key] = 1;for(int k : rooms[key]){dfs(rooms, k, open);}}
public:bool canVisitAllRooms(vector<vector<int>>& rooms) {vector<int> open(rooms.size());dfs(rooms, 0, open);for(int p : open){if(p == 0) return false;}return true;}
};

Java

class Solution {private void dfs(List<List<Integer>> rooms, int key, int[] open){if(open[key] == 1) return;open[key] = 1;for(int k : rooms.get(key)){dfs(rooms, k, open);}}public boolean canVisitAllRooms(List<List<Integer>> rooms) {int[] open = new int[rooms.size()];dfs(rooms, 0, open);for(int p : open){if(p == 0) return false;}return true;}
}

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n + m ) O(n + m) O(n+m),其中 n 为房间的数量,m 是所有房间中的钥匙数量的总数。
  • 空间复杂度 O ( n ) O(n) O(n),主要为队列(bfs)或栈空间(dfs)的开销。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/685987.html

相关文章

打开“管理加载项”

问题描述&#xff1a; “管理加载项”没有找到&#xff0c;不知道怎么打开。 解决方案&#xff1a; IE浏览器右上角三个点–>使用Internet explorer打–>IE右上角的 “工具”按钮–>管理加载项 &#xff08;实验版本&#xff1a; IE 11&#xff09; 360安全浏览器右…

Win10 calc.exe 无法打开计算器的解决方法

Win10 calc.exe 无法打开计算器的解决方法 参考文章&#xff1a; &#xff08;1&#xff09;Win10 calc.exe 无法打开计算器的解决方法 &#xff08;2&#xff09;https://www.cnblogs.com/xingyunblog/p/10470169.html 备忘一下。

win10 自带计算器删除了怎么办

Powershell&#xff0c;以管理员身份运行后&#xff0c;使用下面的命令&#xff1a; 重要的说三遍&#xff1a;以管理员身份运行&#xff01;以管理员身份运行&#xff01;以管理员身份运行&#xff01; Get-AppxPackage -allusers | Select Name, PackageFullName Add-appxpa…

使用Windows10计算器计算得出的结果明显错误,怎么办?

使用Windows10计算器计算得出的结果明显错误&#xff0c;怎么办&#xff1f; 背景 今天在使用电脑自带的计算器时&#xff0c;呼呼呼敲了一串式子算出了一个结果。 那么大家有没有发现哪里不对劲呢&#xff1f;哈哈&#xff0c;对了&#xff0c;当时的我是一脸懵——这结果明…

无法加载计算机管理,电脑中无法打开Internet选项中的管理加载项如何解决

‍ 在我们使用的浏览器中有许多插件&#xff0c;通过这些插件可以实现播放Flash、进行下载等功能&#xff0c;但是浏览器中同时也会存在一些对我们而言无用的插件&#xff0c;这时候就需要通过管理加载项来进行清理&#xff0c;但有用户发现电脑中无法打开Internet选项中的管理…

win10系统无法打开计算器等应用解决办法

在运行中输入calc后结果提示无法打开&#xff0c;提示联系管理员重新安装且都显示灰色 需要重置一下win10的内置应用程序&#xff01; 做法&#xff1a;在Cortana搜索栏输入PowerShell后&#xff0c;在第一项点击右键&#xff0c;选择“以管理员身份运行” 打开后输入&#xf…

科学计算机显示stat,科学计算器在统计功能中如何清除以前不需要的数据。

满意答案 ybb630 2013.06.29 采纳率&#xff1a;47% 等级&#xff1a;12 已帮助&#xff1a;7924人 计算器的统计功能&#xff1a; 一、进入统计计算功能状态 类型1&#xff1a; 按ON/C键&#xff0c;再按2ndF键&#xff0c;再按ON/C键&#xff0c;进入统计计算功能状态。液…

win10老是弹出计算机管理器,win10系统Ie11老是弹出“管理加载项”提示框取消的处理办法...

有时候可能会遇到对win10系统IE11老是弹出“管理加载项”提示框取消进行设置&#xff0c;如果我们需要对win10系统IE11老是弹出“管理加载项”提示框取消进行设置时&#xff0c;要怎么处理win10系统IE11老是弹出“管理加载项”提示框取消呢&#xff1f; 接下来给大家带来win10系…

[已解决]关于win10计算器无法使用的问题

这几天win10计算器突然无法打开&#xff0c;在开始菜单中变成这个样子 点击启动是出现这样的问提示 去微软商店更新也提示出现错误 甚至安装第三方计算器也出现错误 所以&#xff0c;直接去控制面板对计算器进行一个卸载 再重新使用本地安装包安装计算器 计算器安装包获取 链…

开始菜单计算器删了,如何添加

用鼠标左键按C:\WINDOWS\system32里住计算器图标不放&#xff0c;把它拖到“开始”图标上&#xff0c;系统会弹出开始菜单&#xff0c;再继续拖到程序上&#xff0c;你会看到附件&#xff0c;然后拖到附件上就可以了。

EXCEL加载项的安装与取消

每次打开excel弹出要安装Microsoft.VisualStudio.QualityTools.LoadTestExcelAddIn.vsto的窗口之前使用excel每次都弹出该窗口的时候&#xff0c;就直接点击“不安装”&#xff0c;然后也可以正常使用excel。但是今天实在受不了了&#xff0c;就网上查了一下&#xff0c;想把这…

计算机管理器用户怎么打开,win10无法使用内置管理员账户打开计算器如何设置...

在使用win10系统时&#xff0c;想必许多用户都有遇到这种情况&#xff0c;那就是系统中的有些程序需要使用到内置管理员账户才能够打开&#xff0c;可是最近有的用户在操作win10系统中内置管理员账户打开计算器却是无法打开&#xff0c;那么win10无法使用内置管理员账户打开计算…

启用和禁用excel 中的加载项

查看已安装的加载项 安装 2007 Microsoft Office System 时&#xff0c;将在计算机上安装多个加载项。 请在以下 2007 Microsoft Office System 程序中执行下列操作&#xff1a; Word、Excel、PowerPoint 或 Access 单击“Microsoft Office 按钮”&#xff0c;然后单击“程序…

删除Windows启动管理器下的加载项

删除Windows启动管理器下的加载项 环境&#xff1a;Windows7操作系统工具&#xff1a;cmd命令行工具操作&#xff1a; > msconfig 系统配置工具> bededit 启动菜单编辑器&#xff0c;命令行工具跳出如下内容&#xff1a; Windows 启动管理器 -------------------- 标识符…

HTML中首加载项,IE浏览器弹出加载项管理如何解决

很多小伙伴们都不清楚IE浏览器弹出加载项管理如何解决&#xff0c;接下来小编带来解决IE浏览器弹出加载项管理方法说明&#xff0c;希望可以帮助到大家。 IE是国内很多人使用的一款浏览器&#xff0c;由于稳定性方面不是很强&#xff0c;所以有的时候就会出现一些小问题&#x…

管理 Office com 加载项

1.启动 Office 产品 (Word, Excel, Outlook ...)。2.在“工具”菜单上&#xff0c;单击“选项”。3.在“其他”选项卡上&#xff0c;执行下列操作之一&#xff1a; •删除 COM 加载项。为此&#xff0c;请按照下列步骤操作&#xff1a; 1.单击“高级选项”。2.在“高级选项”对…

电脑上计算机软件一直自动弹出,win7系统开机一直自动弹出计算器窗口怎么解决...

有不少深度技术win7旗舰版系统用户反映说碰到这样一个情况&#xff0c;就是开机之后就会一直自动弹出计算器窗口&#xff0c;一直显示到满屏卡机到死&#xff0c;遇到这样的问题该怎么办呢&#xff0c;现在随小编一起来看看win7系统开机一直自动弹出计算器窗口的具体解决步骤。…

panda3d 模型转换命令复习学习

在此学习了把maya模型转换为panda3d的egg格式&#xff1b; 在Panda3d中转换Maya模型为egg格式并使用pview查看_panda3d egg文件浏览器_bcbobo21cn的博客-CSDN博客 下面继续看一下模型转换命令&#xff1b;列出带 egg 字符串的命令&#xff1b; 先复习一下&#xff0c;可以把m…

win11操作系统·系统自带计算器找不到了怎么恢复,需要使用新应用以打开此ms-calculator 链接-问题解决

解决打开&#xff1a; 开始菜单运行Windows Powershell 执行 Get-AppXPackage *WindowsStore* -AllUsers | Foreach {Add-AppxPackage -DisableDevelopmentMode -Register "$($_.InstallLocation)\AppXManifest.xml"} 恢复商店 执行 Get-AppxPackage *calculator…
最新文章