leetcode
leetcode 751 ~ 800
钥匙和房间

钥匙和房间

难度:

标签:

题目描述

代码结果

运行时间: 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和DFS都可以用来解决这类问题,即遍历图中的所有节点。选择BFS而不是DFS的原因可能是因为BFS在这类问题中通常更直观,因为它按层次遍历节点,从一个房间出发,逐步探索所有可达的房间。BFS能较快地找到离起点近的节点,这在某些情况下可能更为高效。本质上,BFS是用队列实现的,逐层处理节点,而DFS是用栈实现的,它会深入到某一分支的最深处,然后再回溯。在这个特定的问题中,使用BFS或DFS并没有本质区别,因为最终目标是遍历所有节点,检查是否可以访问所有房间。
🦆
在BFS实现中,如果在某一步中一个房间有多把钥匙能打开相同的房间,这会对算法的效率造成什么影响?是否有必要优化去重?
如果一个房间中有多把钥匙可以打开同一个房间,这将导致在队列中出现重复的房间编号,这可能会影响算法的效率,因为同一个房间会被多次加入队列并且其检查过程也会被多次执行。优化去重是有必要的,可以通过在将房间号加入队列之前检查该房间是否已被访问(即已经在队列中或已处理过)来实现。这样可以减少不必要的操作和内存使用,提高算法的效率。
🦆
BFS中使用的队列`q`在最坏情况下可能存储多少个元素?这对内存的使用有何影响?
在最坏的情况下,如果图是高度连接的,即每个房间都能直接或间接地到达其他所有房间,队列`q`可能会存储所有房间的编号,即在某一时刻,队列的大小可能等于房间总数。这种情况下,队列的大小将达到其最大值,即等于房间的总数。这将增大内存的使用,尤其是在房间数量非常多的情景下,可能对系统资源产生较大压力。
🦆
在代码中,`for x in visited: if not x: return False`这段代码是如何保证所有房间都被访问过?是否存在边界情况未被考虑?
这段代码通过遍历`visited`列表来检查每个房间是否被访问过。如果发现有任何一个房间未被访问(即对应的`visited`值为`False`),则立即返回`False`。这种方式确保了只有当所有房间都被访问过时,函数才返回`True`。在这种实现中,没有明显的边界情况未被考虑。然而,如果输入的房间列表为空(即没有房间),根据实现,应当返回`True`,因为不存在未被访问的房间,这是一个需要确认具体业务逻辑是否接受的边界情况。

相关问题