当前位置：首页 > news >正文

算法题钥匙和房间

news 2026/5/12 16:40:29

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}}