钥匙和房间
难度:
标签:
题目描述
代码结果
运行时间: 23 ms, 内存: 16.4 MB
/*
* 思路:
* 1. 使用Stream API简化访问逻辑。
* 2. 使用一个布尔数组 visited 来记录是否访问过某个房间。
* 3. 使用Queue来模拟广度优先搜索(BFS)访问每个房间。
* 4. 初始时将第一个房间(0号房间)设为已访问并加入队列。
* 5. 从队列中取出房间,使用stream遍历获取到的钥匙并解锁相应房间。
* 6. 最后检查是否所有房间都已访问,如果是则返回 true,否则返回 false。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
boolean[] visited = new boolean[rooms.size()];
visited[0] = true;
Queue<Integer> queue = new LinkedList<>();
queue.add(0);
while (!queue.isEmpty()) {
int room = queue.poll();
rooms.get(room).stream()
.filter(key -> !visited[key])
.forEach(key -> {
visited[key] = true;
queue.add(key);
});
}
return IntStream.range(0, visited.length).allMatch(i -> visited[i]);
}
}
解释
方法:
题解采用了广度优先搜索(BFS)的方法来遍历所有房间,检查是否能进入每个房间。首先,创建一个布尔列表visited来记录每个房间是否被访问过,初始化为False。BFS从房间0开始,将房间0标记为已访问。然后,使用队列来处理接下来的房间,队列中存储着待访问的房间。对于队列中的每个房间,检查该房间内的所有钥匙,如果该钥匙对应的房间未被访问,则将其加入队列,并标记为已访问。循环处理直到队列为空。最后,检查visited列表,如果所有房间都被访问过,则返回true,否则返回false。
时间复杂度:
O(n + m)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么选择广度优先搜索(BFS)而不是深度优先搜索(DFS)来解决这个问题?两者在处理这类问题上有什么本质的区别吗?
▷🦆
在BFS实现中,如果在某一步中一个房间有多把钥匙能打开相同的房间,这会对算法的效率造成什么影响?是否有必要优化去重?
▷🦆
BFS中使用的队列`q`在最坏情况下可能存储多少个元素?这对内存的使用有何影响?
▷🦆
在代码中,`for x in visited: if not x: return False`这段代码是如何保证所有房间都被访问过?是否存在边界情况未被考虑?
▷