leetCode 841. 钥匙和房间 图遍历 深度优先遍历+广度优先遍历 + 图解

2023-11-28 23:20

本文主要是介绍leetCode 841. 钥匙和房间 图遍历 深度优先遍历+广度优先遍历 + 图解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

841. 钥匙和房间 - 力扣(LeetCode)

有 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 号房间。


(1)图的深度优先遍历: 

思路:使用深度优先搜索的方式遍历整张图,统计可以到达的节点个数,并利用数组 visit 记录当前节点是否访问过,避免重复访问

class Solution {
public:vector<bool> visit;int visCount=0;void dfs(vector<vector<int>>& rooms,int roomId){visit[roomId] = true;visCount++;for(auto& roomKey:rooms[roomId]) {if(!visit[roomKey]) {dfs(rooms,roomKey);}}}bool canVisitAllRooms(vector<vector<int>>& rooms) {int n = rooms.size();// 房间个数visit.resize(n);dfs(rooms,0);return visCount == n;}
};

分析复杂度:

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

(2)图的广度优先遍历:

思路:使用广度优先搜索的方式遍历整张图,统计可以到达的节点个数,并利用数组 visit 记录当前节点是否访问过,避免重复访问

class Solution {
public:bool canVisitAllRooms(vector<vector<int>>& rooms) {int n = rooms.size(),visCount=0;vector<bool> visit(n,0);visit[0]=true;queue<int> Q;Q.emplace(0);while(!Q.empty()) {int roomId = Q.front();Q.pop();visCount++;for(auto& roomKey : rooms[roomId]) {if(!visit[roomKey]) {visit[roomKey] = true;Q.emplace(roomKey);}}   }return visCount==n;}
};

分析复杂度:

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

推荐和参考文章:

841. 钥匙和房间 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/keys-and-rooms/solutions/395157/shou-hua-tu-jie-you-xiang-tu-de-bian-li-yi-jing-ge/841. 钥匙和房间 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/keys-and-rooms/solutions/393524/yao-chi-he-fang-jian-by-leetcode-solution/

这篇关于leetCode 841. 钥匙和房间 图遍历 深度优先遍历+广度优先遍历 + 图解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/430574

相关文章

深度解析Java DTO(最新推荐)

《深度解析JavaDTO(最新推荐)》DTO(DataTransferObject)是一种用于在不同层(如Controller层、Service层)之间传输数据的对象设计模式,其核心目的是封装数据,... 目录一、什么是DTO?DTO的核心特点:二、为什么需要DTO?(对比Entity)三、实际应用场景解析

深度解析Java项目中包和包之间的联系

《深度解析Java项目中包和包之间的联系》文章浏览阅读850次,点赞13次,收藏8次。本文详细介绍了Java分层架构中的几个关键包:DTO、Controller、Service和Mapper。_jav... 目录前言一、各大包1.DTO1.1、DTO的核心用途1.2. DTO与实体类(Entity)的区别1

深度解析Python装饰器常见用法与进阶技巧

《深度解析Python装饰器常见用法与进阶技巧》Python装饰器(Decorator)是提升代码可读性与复用性的强大工具,本文将深入解析Python装饰器的原理,常见用法,进阶技巧与最佳实践,希望可... 目录装饰器的基本原理函数装饰器的常见用法带参数的装饰器类装饰器与方法装饰器装饰器的嵌套与组合进阶技巧

深度解析Spring Boot拦截器Interceptor与过滤器Filter的区别与实战指南

《深度解析SpringBoot拦截器Interceptor与过滤器Filter的区别与实战指南》本文深度解析SpringBoot中拦截器与过滤器的区别,涵盖执行顺序、依赖关系、异常处理等核心差异,并... 目录Spring Boot拦截器(Interceptor)与过滤器(Filter)深度解析:区别、实现

深度解析Spring AOP @Aspect 原理、实战与最佳实践教程

《深度解析SpringAOP@Aspect原理、实战与最佳实践教程》文章系统讲解了SpringAOP核心概念、实现方式及原理,涵盖横切关注点分离、代理机制(JDK/CGLIB)、切入点类型、性能... 目录1. @ASPect 核心概念1.1 AOP 编程范式1.2 @Aspect 关键特性2. 完整代码实

SpringBoot开发中十大常见陷阱深度解析与避坑指南

《SpringBoot开发中十大常见陷阱深度解析与避坑指南》在SpringBoot的开发过程中,即使是经验丰富的开发者也难免会遇到各种棘手的问题,本文将针对SpringBoot开发中十大常见的“坑... 目录引言一、配置总出错?是不是同时用了.properties和.yml?二、换个位置配置就失效?搞清楚加

MySQL存储过程之循环遍历查询的结果集详解

《MySQL存储过程之循环遍历查询的结果集详解》:本文主要介绍MySQL存储过程之循环遍历查询的结果集,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言1. 表结构2. 存储过程3. 关于存储过程的SQL补充总结前言近来碰到这样一个问题:在生产上导入的数据发现

Python中文件读取操作漏洞深度解析与防护指南

《Python中文件读取操作漏洞深度解析与防护指南》在Web应用开发中,文件操作是最基础也最危险的功能之一,这篇文章将全面剖析Python环境中常见的文件读取漏洞类型,成因及防护方案,感兴趣的小伙伴可... 目录引言一、静态资源处理中的路径穿越漏洞1.1 典型漏洞场景1.2 os.path.join()的陷

python进行while遍历的常见错误解析

《python进行while遍历的常见错误解析》在Python中选择合适的遍历方式需要综合考虑可读性、性能和具体需求,本文就来和大家讲解一下python中while遍历常见错误以及所有遍历方法的优缺点... 目录一、超出数组范围问题分析错误复现解决方法关键区别二、continue使用问题分析正确写法关键点三

Spring Boot拦截器Interceptor与过滤器Filter深度解析(区别、实现与实战指南)

《SpringBoot拦截器Interceptor与过滤器Filter深度解析(区别、实现与实战指南)》:本文主要介绍SpringBoot拦截器Interceptor与过滤器Filter深度解析... 目录Spring Boot拦截器(Interceptor)与过滤器(Filter)深度解析:区别、实现与实