841. 钥匙和房间

本文主要是介绍841. 钥匙和房间，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：

841. 钥匙和房间

https://leetcode.cn/problems/keys-and-rooms/description/

完成情况：

解题思路：

这段代码是一个解决问题的类，其中包含了一个私有方法dfs和一个公共方法canVisitAllRooms。dfs方法使用深度优先搜索（DFS）算法来遍历房间，同时记录哪些房间被访问过。canVisitAllRooms方法则调用dfs方法来检查是否可以访问所有房间。

具体解释如下：

• dfs方法接收一个键值key、房间列表rooms和访问状态列表visited作为参数。如果当前房间已经被访问过，则直接返回；否则标记当前房间为已访问，并递归地对当前房间可以到达的房间进行深度优先搜索。
• canVisitAllRooms方法接收一个房间列表rooms作为参数。首先创建一个与房间数量相同的访问状态列表visited，并调用dfs方法从第一个房间开始遍历。最后检查visited列表中是否所有房间都被访问过，若有未被访问的房间则返回false，否则返回true。

这段代码的主要功能是使用DFS算法来检查是否可以访问所有的房间，通过标记访问状态来避免重复访问，并最终返回一个布尔值表示是否可以访问所有房间。

参考代码：

_841钥匙和房间_dfs

package 代码随想录.图论;import java.util.ArrayList;
import java.util.List;public class _841钥匙和房间_dfs {/*** 房间编号从0开始计算 ，每个List<Integer>存储一个集合，集合里表示能去的所有方便* @param rooms* @return*/public boolean canVisitAllRooms(List<List<Integer>> rooms) {//dfs，看看能不能遍历到所有的节点即可。//先构造一个visited数组用来最后判别是否能访问到所有的节点List<Boolean> visited = new ArrayList<Boolean>(){{//并为里面rooms.size()尺寸赋值全falsefor (int i = 0; i < rooms.size();i++) {add(false);}}};dfs_canVisitAllRooms(0,rooms,visited);//检查是否都访问到了for (boolean flag : visited){if (!flag){return false;}}return true;}private void dfs_canVisitAllRooms(int idx_key, List<List<Integer>> rooms, List<Boolean> visited) {if (visited.get(idx_key)){return;}visited.set(idx_key,true);for (int k : rooms.get(idx_key)){//递归dfs_canVisitAllRooms(k,rooms,visited);}}
}

_841钥匙和房间_bfs

package 代码随想录.图论;import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;public class _841钥匙和房间_bfs {/*** 房间编号从0开始计算 ，每个List<Integer>存储一个集合，集合里表示能去的所有方便* @param rooms* @return*/public boolean canVisitAllRooms(List<List<Integer>> rooms) {//先构造一个visited数组用来最后判别是否能访问到所有的节点boolean visited [] = new boolean[rooms.size()];visited[0] = true;Deque<Integer> queueList = new ArrayDeque<Integer>();queueList.add(0);   //加入一号房间while (!queueList.isEmpty()){//遍历，并不断加入新的节点int curNode_Key = queueList.poll();//再去对应位置获取所有的元素加入queueList，然后进行判断，然后迭代for (int key : rooms.get(curNode_Key)){if (visited[key])   continue;visited[key] = true;queueList.add(key);}}for (boolean key_visit : visited){if (!key_visit) return false;}return true;}
}

错误经验吸取

这篇关于841. 钥匙和房间的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---