LeetCode 841. 钥匙和房间 题目描述 有 n 个房间，编号从 0 到 n-1 。每个房间都有一些钥匙（可以打开其他房间）。你最初在房间 0``，其他房间的门默认锁着。给你一个数组 rooms ，其中 rooms[ i] 是你进入房间 i 后能得到的钥匙集合（即可以进入的房间编号列表）。如果能进入所有房间，返回 true ；否则返回 false ` 。 示例 输入： rooms = [[1],[2],[3],[]] 输出： true 解释：从房间 0 出发，拿到钥匙 1 → 进入房间 1，拿到钥匙 2 → 进入房间 2，拿到钥匙 3 → 进入房间 3，所有房间均可进入。 解题过程 问题分析 房间和钥匙的关系可以抽象为 有向图 ：每个房间是节点，钥匙是指向其他节点的边。 目标：判断从节点 0 出发，是否能遍历所有节点（即图的连通性判断）。 算法选择 适合用 深度优先搜索（DFS） 或 广度优先搜索（BFS） 模拟遍历过程。 使用一个集合（如数组）记录已访问的房间，避免重复访问。 DFS 实现步骤 初始化一个长度为 n 的布尔数组 visited ，标记房间是否被访问过。 从房间 0 开始递归： 标记当前房间为已访问。 遍历当前房间的所有钥匙，对每个未访问过的房间递归调用 DFS。 最后检查 visited 中是否所有房间都被访问到。 示例推导 以 rooms = [[1,3],[3,0,1],[2],[0]] 为例： 从房间 0 开始：访问 0，拿到钥匙 [ 1,3 ]。 进入房间 1：拿到钥匙 [ 3,0,1 ]，但 0 已访问，只进入未访问的房间 3。 进入房间 3：拿到钥匙 [ 0 ]，无新房间可进，回溯。 进入房间 3（已访问过，跳过）。 此时未访问房间 2，但无法从已访问房间拿到钥匙 2，因此返回 false 。 优化与边界情况 如果某次访问后已访问房间数等于 n ，可提前终止。 注意空房间（如 rooms[i] = [] ）的情况。 关键点 将问题转化为图的遍历问题，使用 DFS/BFS 记录访问状态。 时间复杂度：O(n + k)（n 为房间数，k 为总钥匙数）。 空间复杂度：O(n)（存储访问状态和递归栈）。