当前位置: 首页 > news >正文

力扣第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,表示所有房间都被成功访问了}
}

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

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

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

相关文章:

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

题目 841. 钥匙和房间 中等 相关标签 深度优先搜索 广度优先搜索 图 有 n 个房间&#xff0c;房间按从 0 到 n - 1 编号。最初&#xff0c;除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而&#xff0c;你不能在没有获得钥匙的时候进入锁住的房间…...

React 中 react-i18next 切换语言( 项目国际化 )

背景 平时中会遇到需求&#xff0c;就是切换语言&#xff0c;语种等。其实总的来说都是用i18n来实现的 思路 首先在项目中安装i18n插件&#xff0c;然后将插件引入到项目&#xff0c;然后配置语言包&#xff08;语言包需要你自己来进行配置&#xff0c;自己编写语言包&#xff…...

antd design 5 版本 文件上传

<UploadcustomRequest{customRequest}accept".csv" showUploadList{false}><Button icon{<UploadOutlined />}>上传 CSV 文件</Button></Upload> accept 代表限制的上传类型 也可设置 .excel // 文件上传 ( CSV ) const customReques…...

【如何学习Python自动化测试】—— 浏览器操作

4 、 浏览器操作 4.1 浏览器最大化 Webdriver 打开浏览器后&#xff0c;默认不是最大化&#xff0c;如果需要界面最大化&#xff0c;需要通过 maximize_window()方法来实现&#xff0c;代码如下&#xff1a; maximize_window()方法是Selenium WebDriver提供的一个方法&#xf…...

Python编程技巧 – 使用字典

Python编程技巧 – 使用字典 Python Programming Skills – Using Dictionary Dictionary, 即字典&#xff0c;这是Python语言的一种重要的数据结构&#xff1b;Python字典是以键&#xff08;key&#xff09;值(value)对为元素&#xff0c;来存储数据的集合。 前文提到Python列…...

el-tree 与table表格联动

html部分 <div class"org-left"><el-input v-model"filterText" placeholder"" size"default" /><el-tree ref"treeRef" class"filter-tree" :data"treeData" :props"defaultProp…...

Leetcode刷题详解——删除并获得点数

1. 题目链接&#xff1a;740. 删除并获得点数 2. 题目描述&#xff1a; 给你一个整数数组 nums &#xff0c;你可以对它进行一些操作。 每次操作中&#xff0c;选择任意一个 nums[i] &#xff0c;删除它并获得 nums[i] 的点数。之后&#xff0c;你必须删除 所有 等于 nums[i] …...

HTTP四种请求方式,状态码,请求和响应报文

1.get请求 一般用于获取数据请求参数在URL后面请求参数的大小有限制 2.post请求 一般用于修改数据提交的数据在请求体中提交数据的大小没有限制 3.put请求 一般用于添加数据 4.delete请求 一般用于删除数据 5.一次完整的http请求过程 域名解析&#xff1a;使用DNS协议…...

Python - Wave2lip 环境配置与 Wave2lip x GFP-GAN 实战 [超详细!]

一.引言 前面介绍了 GFP-GAN 的原理与应用&#xff0c;其用于优化图像画质。本文关注另外一个相关的项目 Wave2lip&#xff0c;其可以通过人物视频与自定义音频进行适配&#xff0c;改变视频中人物的嘴型与音频对应。 二.Wave2Lip 简介 Wave2lip 研究 lip-syncing 以达到视频…...

2311rust,1.31版本更新

1.31.0稳定版 Rust1.31可能是最激动人心的版本! 使用Cargo创建一个新项目: cargo new foo以下是Cargo.toml的内容: [package] name "foo" version "0.1.0" authors ["名字"] edition "2018" //版本. [dependencies]在[package]…...

文心一言-情感关怀之旅

如何让LLM更有温度。 应用介绍...

下厨房网站月度最佳栏目菜谱数据获取及分析PLus

目录 概要 源数据获取 写Python代码爬取数据 Scala介绍与数据处理 1.Sacla介绍 2.Scala数据处理流程 数据可视化 最终大屏效果 小结 概要 本文的主题是获取下厨房网站月度最佳栏目近十年数据&#xff0c;最终进行数据清洗、处理后生成所需的数据库表&#xff0c;最终进…...

buildadmin+tp8表格操作(5)自定义组装搜索的查询

有时候我们会自定义组装一些数据&#xff0c;发送给后端&#xff0c;让后端来进行筛选&#xff0c;这里有一个示例 const onComSearchIdEq () > {// 展开公共搜索baTable.table.showComSearch true/*** 公共搜索表单赋值* 范围搜索有两个输入框&#xff0c;输入框绑定变量…...

企业级固态硬盘如何稳定运行?永铭固液混合铝电解电容来帮忙

企业级 固态硬盘 永铭固液混合铝电解电容 企业级固态硬盘&#xff08;SSD&#xff09;主要应用于互联网、云服务、金融和电信等客户的数据中心&#xff0c;企业级SSD具备更快传输速度、更大单盘容量、更高使用寿命以及更高的可靠性要求。 企业级固态硬盘的运行要求—固液混合电…...

【MISRA C 2012】Rule 4.2 不应该使用三连符

1. 规则1.1 原文1.2 分类 2. 关键描述3. 代码实例 1. 规则 1.1 原文 Rule 4.2 Trigraphs should not be used Category Advisory Analysis Decidable, Single Translation Unit Applies to C90, C99 1.2 分类 规则4.2&#xff1a;不应该使用三连符 Advisory建议类规范。 2…...

spring boot加mybatis puls实现,在新增/修改时,对某些字段进行处理,使用的@TableField()

1.先说场景&#xff0c;在对mysql数据库表数据插入或者更新时都得记录时间和用户id 传统实现有点繁琐&#xff0c;这里还可以封装一下公共方法。 2.解决方法&#xff1a; 2.1&#xff1a;使用aop切面编程&#xff08;记录一下&#xff0c;有时间再攻克&#xff09;。 2.2&…...

如何构建风险矩阵?3大注意事项

风险矩阵法&#xff08;RMA&#xff09;是确定威胁优先级别的最有效工具之一&#xff0c;可以帮助项目团队识别和评估项目中的风险&#xff0c;帮助项目团队对风险进行排序&#xff0c;清晰地展示风险的可能性和严重性&#xff0c;为项目团队制定风险管理策略提供依据。 如果没…...

SpringSecurity5|12.实现RememberMe 及 实现原理分析

security/day08 这个功能大家还熟悉么&#xff1f;我们在登录网站的时候&#xff0c;除了让你输入用户名和密码&#xff0c;还会有个勾选框&#xff1a; 记住我&#xff01;&#xff01;&#xff01;不是让大家记住我哈。 值得一提的是&#xff0c;Spring Security 也提供了这个…...

持续集成交付CICD:Jenkins Sharedlibrary 共享库

目录 一、理论 1.共享库 2.共享库配置 3.使用共享库 4.共享库扩展 二、实验 1.连接共享库 2.使用共享库 三、问题 1.路径报错 2.readJSON 报错 一、理论 1.共享库 &#xff08;1&#xff09;概念 1&#xff09;共享库这并不是一个全新的概念&#xff0c;其实在编…...

Linux--网络编程

一、网络编程概述1.进程间通信&#xff1a; 1&#xff09;进程间通信的方式有**&#xff1a;管道&#xff0c;消息队列&#xff0c;共享内存&#xff0c;信号&#xff0c;信号量这么集中 2&#xff09;特点&#xff1a;依赖于linux内核&#xff0c;基本是通过内核来实现应用层…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...