长沙市网站建设_网站建设公司_C#_seo优化

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）：

1. 建模：

   • 将房间看作图的节点，钥匙看作有向边
   • 问题转化为：从节点0出发，能否访问所有节点？

2. 遍历：

   • 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递归过程：

1. 访问房间0：visited = [true, false, false, false]

   • 钥匙：[1]
   • 递归访问房间1

2. 访问房间1：visited = [true, true, false, false]

   • 钥匙：[2]
   • 递归访问房间2

3. 访问房间2：visited = [true, true, true, false]

   • 钥匙：[3]
   • 递归访问房间3

4. 访问房间3：visited = [true, true, true, true]

   • 钥匙：[]
   • 返回

5. 检查结果：所有房间都已访问 →true

2：rooms = [[1,3],[3,0,1],[2],[0]]

DFS递归过程：

1. 访问房间0：visited = [true, false, false, false]

   • 钥匙：[1, 3]
   • 先递归访问房间1

2. 访问房间1：visited = [true, true, false, false]

   • 钥匙：[3, 0, 1]
   • 房间3未访问，递归访问房间3
   • 房间0和1已访问，跳过

3. 访问房间3：visited = [true, true, false, true]

   • 钥匙：[0]
   • 房间0已访问，跳过
   • 返回到房间1，再返回到房间0

4. 回到房间0：处理钥匙3（已访问），结束

5. 检查结果：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}}

关键点

1. 图遍历：

   • 房间是节点，钥匙是有向边
   • 问题等价于判断从节点0出发是否能到达所有节点

2. 起始条件：

   • 保证可以从房间0开始（不需要钥匙）
   • 这是连通性判断的起点

3. 访问标记：

   • 避免重复访问和无限循环
   • 环形结构（如房间0→1→2→0）需要正确处理

常见问题

1. 为什么不需要考虑钥匙的使用顺序？
   能否访问所有房间，而不是访问的顺序。只要存在一条路径能到达某个房间，就认为可以访问。

2. DFS和BFS有什么区别？
   在这个问题中，两种方法的结果完全相同。DFS可能会更快到达某些房间，BFS按层次访问，最终的可达性判断是一样的。