如何快速找到做网站的客户,pc端好玩的大型网游,国际空间站vs中国空间站,网站查询ip地址查询#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域优质创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ DFS 求解思路 实现代码 运行结果 共勉 题目链接
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] 的值 互不相同 求解思路实现代码运行结果 ⚡ DFS 求解思路
该题通过DFS或者BFS来实现从0位置开始去找到可以从当前list.get(0)集合中所有可去向的房间如果当前位置没有走过计数加1。递归结束后判断此时cnt和房间的个数是否相等如果相等返回true否则返回false。有了基本的思路接下来我们就来通过代码来实现一下递归和迭代的解法。 实现代码
class Solution {ListListInteger rooms;boolean[] flag;int cnt;int n;public boolean canVisitAllRooms(ListListInteger rooms) {this.rooms rooms;this.flag new boolean[rooms.size()];this.cnt 0;dfs(0);return cnt rooms.size();}private void dfs(int i) {cnt;flag[i] true;for (int next : rooms.get(i)) {if (!flag[next])dfs(next);}}}运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
