841. 钥匙和房间
问题描述
有n个房间，编号从0到n-1。每个房间都有一些钥匙，可以打开其他房间。
给定一个数组rooms，其中rooms[i]是一个列表，表示你进入房间i后可以拿到的所有钥匙（钥匙对应房间的编号）。
你从房间0开始，初始时可以进入房间0。
返回true如果你可以进入所有房间，否则返回false。
示例：
输入:rooms=[[1],[2],[3],[]]输出:true解释:-从房间0开始，拿到钥匙1-用钥匙1进入房间1，拿到钥匙2-用钥匙2进入房间2，拿到钥匙3-用钥匙3进入房间3-所有房间都已访问输入:rooms=[[1,3],[3,0,1],[2],[0]]输出:false解释:-从房间0开始，拿到钥匙1和3-可以进入房间1和3，但无法进入房间2-房间2中有钥匙2，但无法获得算法思路
图的遍历（DFS/BFS）：
建模：
- 将房间看作图的节点，钥匙看作有向边
- 问题转化为：从节点0出发，能否访问所有节点？
遍历：
- DFS（深度优先搜索）：递归或栈实现
- BFS（广度优先搜索）：队列实现
代码实现
方法一：DFS递归
importjava.util.*;classSolution{/** * 判断是否能进入所有房间 * 使用DFS递归遍历，从房间0开始 * * @param rooms 房间钥匙信息，rooms[i]表示房间i中的钥匙列表 * @return 如果能进入所有房间返回true，否则返回false */publicbooleancanVisitAllRooms(List<List<Integer>>rooms){intn=rooms.size();boolean[]visited=newboolean[n];// 记录房间访问状态// 从房间0开始DFSdfs(rooms,0,visited);// 检查是否所有房间都被访问for(booleanroomVisited:visited){if(!roomVisited){returnfalse;}}returntrue;}/** * 深度优先搜索遍历房间 * * @param rooms 房间钥匙信息 * @param room 当前房间编号 * @param visited 访问状态数组 */privatevoiddfs(List<List<Integer>>rooms,introom,boolean[]visited){// 标记当前房间为已访问visited[room]=true;// 遍历当前房间中的所有钥匙for(intkey:rooms.get(room)){// 如果对应的房间未访问过，递归访问if(!visited[key]){dfs(rooms,key,visited);}}}}方法二：DFS栈实现
importjava.util.*;classSolution{/** * 使用栈实现DFS遍历 */publicbooleancanVisitAllRooms(List<List<Integer>>rooms){intn=rooms.size();boolean[]visited=newboolean[n];Stack<Integer>stack=newStack<>();// 从房间0开始stack.push(0);visited[0]=true;intvisitedCount=1;// 已访问房间数while(!stack.isEmpty()){intcurrentRoom=stack.pop();// 遍历当前房间的所有钥匙for(intkey:rooms.get(currentRoom)){if(!visited[key]){visited[key]=true;stack.push(key);visitedCount++;// 如果已经访问了所有房间，提前结束if(visitedCount==n){returntrue;}}}}returnvisitedCount==n;}}方法三：BFS队列实现
importjava.util.*;classSolution{/** * 使用BFS（队列）实现遍历 */publicbooleancanVisitAllRooms(List<List<Integer>>rooms){intn=rooms.size();boolean[]visited=newboolean[n];Queue<Integer>queue=newLinkedList<>();// 从房间0开始queue.offer(0);visited[0]=true;intvisitedCount=1;while(!queue.isEmpty()){intcurrentRoom=queue.poll();// 遍历当前房间的所有钥匙for(intkey:rooms.get(currentRoom)){if(!visited[key]){visited[key]=true;queue.offer(key);visitedCount++;// 提前结束if(visitedCount==n){returntrue;}}}}returnvisitedCount==n;}}方法四：使用Set记录访问状态
importjava.util.*;classSolution{/** * 使用Set记录已访问房间 */publicbooleancanVisitAllRooms(List<List<Integer>>rooms){Set<Integer>visited=newHashSet<>();Stack<Integer>stack=newStack<>();stack.push(0);while(!stack.isEmpty()){introom=stack.pop();visited.add(room);for(intkey:rooms.get(room)){if(!visited.contains(key)){stack.push(key);}}}returnvisited.size()==rooms.size();}}算法分析
- 时间复杂度：O(N + K)
- N 是房间数量
- K 是所有钥匙的总数（图中边的数量）
- 每个房间和每把钥匙最多被访问一次
- 空间复杂度：O(N)
visited数组：O(N)- 递归栈/显式栈/队列：最坏情况下 O(N)
- 总体空间复杂度为 O(N)
算法过程
1：rooms = [[1],[2],[3],[]]
DFS递归过程：
访问房间0：
visited = [true, false, false, false]- 钥匙：[1]
- 递归访问房间1
访问房间1：
visited = [true, true, false, false]- 钥匙：[2]
- 递归访问房间2
访问房间2：
visited = [true, true, true, false]- 钥匙：[3]
- 递归访问房间3
访问房间3：
visited = [true, true, true, true]- 钥匙：[]
- 返回
检查结果：所有房间都已访问 →
true
2：rooms = [[1,3],[3,0,1],[2],[0]]
DFS递归过程：
访问房间0：
visited = [true, false, false, false]- 钥匙：[1, 3]
- 先递归访问房间1
访问房间1：
visited = [true, true, false, false]- 钥匙：[3, 0, 1]
- 房间3未访问，递归访问房间3
- 房间0和1已访问，跳过
访问房间3：
visited = [true, true, false, true]- 钥匙：[0]
- 房间0已访问，跳过
- 返回到房间1，再返回到房间0
回到房间0：处理钥匙3（已访问），结束
检查结果：
visited = [true, true, false, true]，房间2未访问 →false
测试用例
importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：可以访问所有房间List<List<Integer>>rooms1=Arrays.asList(Arrays.asList(1),Arrays.asList(2),Arrays.asList(3),Arrays.asList());System.out.println("Test 1: "+solution.canVisitAllRooms(rooms1));// true// 测试用例2：无法访问所有房间List<List<Integer>>rooms2=Arrays.asList(Arrays.asList(1,3),Arrays.asList(3,0,1),Arrays.asList(2),Arrays.asList(0));System.out.println("Test 2: "+solution.canVisitAllRooms(rooms2));// false// 测试用例3：只有一个房间List<List<Integer>>rooms3=Arrays.asList(Arrays.asList());System.out.println("Test 3: "+solution.canVisitAllRooms(rooms3));// true// 测试用例4：两个房间，互相有钥匙List<List<Integer>>rooms4=Arrays.asList(Arrays.asList(1),Arrays.asList(0));System.out.println("Test 4: "+solution.canVisitAllRooms(rooms4));// true// 测试用例5：两个房间，单向有钥匙List<List<Integer>>rooms5=Arrays.asList(Arrays.asList(1),Arrays.asList());System.out.println("Test 5: "+solution.canVisitAllRooms(rooms5));// true// 测试用例6：两个房间，没有钥匙List<List<Integer>>rooms6=Arrays.asList(Arrays.asList(),Arrays.asList());System.out.println("Test 6: "+solution.canVisitAllRooms(rooms6));// false// 测试用例7：复杂情况List<List<Integer>>rooms7=Arrays.asList(Arrays.asList(1,2,3),Arrays.asList(2,3),Arrays.asList(3),Arrays.asList());System.out.println("Test 7: "+solution.canVisitAllRooms(rooms7));// true// 测试用例8：环形结构List<List<Integer>>rooms8=Arrays.asList(Arrays.asList(1),Arrays.asList(2),Arrays.asList(0));System.out.println("Test 8: "+solution.canVisitAllRooms(rooms8));// true// 测试用例9：多个分支List<List<Integer>>rooms9=Arrays.asList(Arrays.asList(1,2),Arrays.asList(3),Arrays.asList(4),Arrays.asList(),Arrays.asList());System.out.println("Test 9: "+solution.canVisitAllRooms(rooms9));// true}}关键点
图遍历：
- 房间是节点，钥匙是有向边
- 问题等价于判断从节点0出发是否能到达所有节点
起始条件：
- 保证可以从房间0开始（不需要钥匙）
- 这是连通性判断的起点
访问标记：
- 避免重复访问和无限循环
- 环形结构（如房间0→1→2→0）需要正确处理
常见问题
为什么不需要考虑钥匙的使用顺序？
能否访问所有房间，而不是访问的顺序。只要存在一条路径能到达某个房间，就认为可以访问。DFS和BFS有什么区别？
在这个问题中，两种方法的结果完全相同。DFS可能会更快到达某些房间，BFS按层次访问，最终的可达性判断是一样的。
