当前位置: 首页 > 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;基本是通过内核来实现应用层…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

ui框架-文件列表展示

ui框架-文件列表展示 介绍 UI框架的文件列表展示组件&#xff0c;可以展示文件夹&#xff0c;支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项&#xff0c;适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...

32单片机——基本定时器

STM32F103有众多的定时器&#xff0c;其中包括2个基本定时器&#xff08;TIM6和TIM7&#xff09;、4个通用定时器&#xff08;TIM2~TIM5&#xff09;、2个高级控制定时器&#xff08;TIM1和TIM8&#xff09;&#xff0c;这些定时器彼此完全独立&#xff0c;不共享任何资源 1、定…...

raid存储技术

1. 存储技术概念 数据存储架构是对数据存储方式、存储设备及相关组件的组织和规划&#xff0c;涵盖存储系统的布局、数据存储策略等&#xff0c;它明确数据如何存储、管理与访问&#xff0c;为数据的安全、高效使用提供支撑。 由计算机中一组存储设备、控制部件和管理信息调度的…...

【Redis】Redis从入门到实战:全面指南

Redis从入门到实战:全面指南 一、Redis简介 Redis(Remote Dictionary Server)是一个开源的、基于内存的键值存储系统,它可以用作数据库、缓存和消息代理。由Salvatore Sanfilippo于2009年开发,因其高性能、丰富的数据结构和广泛的语言支持而广受欢迎。 Redis核心特点:…...

中国政务数据安全建设细化及市场需求分析

(基于新《政务数据共享条例》及相关法规) 一、引言 近年来,中国政府高度重视数字政府建设和数据要素市场化配置改革。《政务数据共享条例》(以下简称“《共享条例》”)的发布,与《中华人民共和国数据安全法》(以下简称“《数据安全法》”)、《中华人民共和国个人信息…...