LeetCode 841. 钥匙和房间

Categories:

题目描述
思路分析
1. 解法一：DFS / BFS（推荐）
相似题目

题目描述

✅ 841. 钥匙和房间

思路分析

解法一：DFS / BFS（推荐）

核心思路：

从房间 0 开始遍历，收集可进入的房间。

使用访问数组避免重复进入。

最终检查是否所有房间均可访问。

复杂度分析：

时间复杂度：O(n + m)，其中 n 表示房间数，m 表示钥匙数量。

空间复杂度：O(n)。

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        boolean[] visited = new boolean[rooms.size()];
        dfs(0, rooms, visited);

        for (boolean v : visited) {
            if (!v) {
                return false;
            }
        }
        return true;
    }

    private void dfs(int room, List<List<Integer>> rooms, boolean[] visited) {
        if (visited[room]) {
            return;
        }
        visited[room] = true;
        for (int key : rooms.get(room)) {
            dfs(key, rooms, visited);
        }
    }
}

func canVisitAllRooms(rooms [][]int) bool {
	visited := make([]bool, len(rooms))

	var dfs func(room int)
	dfs = func(room int) {
		if visited[room] {
			return
		}
		visited[room] = true
		for _, key := range rooms[room] {
			dfs(key)
		}
	}

	dfs(0)
	for _, v := range visited {
		if !v {
			return false
		}
	}
	return true
}

相似题目

题目	难度	考察点
797. 所有可能的路径	中等	DFS
841. 钥匙和房间	中等	DFS
200. 岛屿数量	中等	DFS
207. 课程表	中等	图遍历
547. 省份数量	中等	DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/10663250