题目描述
有 N 个房间,开始时你位于 0 号房间。每个房间有不同的号码:0,1,2,…,N-1,并且房间里可能有一些钥匙能使你进入下一个房间。
在形式上,对于每个房间 i 都有一个钥匙列表 rooms[i],每个钥匙 rooms[i][j] 由 [0,1,…,N-1] 中的一个整数表示,其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。
最初,除 0 号房间外的其余所有房间都被锁住。
你可以自由地在房间之间来回走动。
如果能进入每个房间返回 true,否则返回 false。
示例 1:
1 2
| 输入: [[1],[2],[3],[]] 输出: true
|
解释:
我们从 0 号房间开始,拿到钥匙 1。
之后我们去 1 号房间,拿到钥匙 2。
然后我们去 2 号房间,拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间,我们返回 true。
示例 2:
1 2
| 输入:[[1,3],[3,0,1],[2],[0]] 输出:false
|
解释:我们不能进入 2 号房间。
解法
思路:本质上这个题就是把你放进0号房间,考察你是否能走完全部房间。这种提供了一个入口,考察是否能够走完的这类题目,都可以用DFS或BFS来搜索遍历(就如同之前做过的扫雷题目。)
1. 深度优先搜索
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| class Solution { boolean[] flag; int count;
public boolean canVisitAllRooms(List<List<Integer>> rooms) { if (rooms == null) return false; int len = rooms.size(); flag = new boolean[len]; dfs(rooms, 0); return count == len; }
private void dfs(List<List<Integer>> rooms, int num) { flag[num] = true; count++; for (int i: rooms.get(num)) { if (!flag[i]) { dfs(rooms, i); } } } }
|
时间复杂度为$O(nm)$ 房屋总数房间钥匙总数
空间复杂度为$O(n)$ 递归栈空间
2. 广度优先搜素
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
| import java.util.Queue; import java.util.LinkedList;
class Solution { public boolean canVisitAllRooms(List<List<Integer>> rooms) { if (rooms == null) return false; int len = rooms.size(); boolean[] flag = new boolean[len]; int count = 0; Queue<List<Integer>> queue = new LinkedList<>(); queue.offer(rooms.get(0)); count++; flag[0] = true; while(!queue.isEmpty()) { List<Integer> room = queue.poll(); for (int i: room) { if (!flag[i]) { queue.offer(rooms.get(i)); flag[i] = true; count++; } } } return count == len; } }
|
时间复杂度为$O(nm)$ 房屋总数房间钥匙总数
空间复杂度为$O(n)$ 队列空间大小最大为房间总数
参考