| comments | difficulty | edit_url | tags | |||
|---|---|---|---|---|---|---|
true |
中等 |
|
有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。
当你进入一个房间，你可能会在里面找到一套 不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。
给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。
示例 1：
输入：rooms = [[1],[2],[3],[]] 输出：true 解释： 我们从 0 号房间开始，拿到钥匙 1。 之后我们去 1 号房间，拿到钥匙 2。 然后我们去 2 号房间，拿到钥匙 3。 最后我们去了 3 号房间。 由于我们能够进入每个房间，我们返回 true。
示例 2：
输入：rooms = [[1,3],[3,0,1],[2],[0]] 输出：false 解释：我们不能进入 2 号房间。
提示：
n == rooms.length2 <= n <= 10000 <= rooms[i].length <= 10001 <= sum(rooms[i].length) <= 30000 <= rooms[i][j] < n- 所有
rooms[i]的值 互不相同
我们可以使用深度优先搜索的方法遍历整张图，统计可以到达的节点个数，并利用数组 vis 标记当前节点是否访问过，以防止重复访问。
最后统计访问过的节点个数，若与节点总数相同则说明可以访问所有节点，否则说明存在无法到达的节点。
时间复杂度
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
def dfs(i: int):
if i in vis:
return
vis.add(i)
for j in rooms[i]:
dfs(j)
vis = set()
dfs(0)
return len(vis) == len(rooms)class Solution {
private int cnt;
private boolean[] vis;
private List<List<Integer>> g;
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
g = rooms;
vis = new boolean[g.size()];
dfs(0);
return cnt == g.size();
}
private void dfs(int i) {
if (vis[i]) {
return;
}
vis[i] = true;
++cnt;
for (int j : g.get(i)) {
dfs(j);
}
}
}class Solution {
public:
bool canVisitAllRooms(vector<vector<int>>& rooms) {
int n = rooms.size();
int cnt = 0;
bool vis[n];
memset(vis, false, sizeof(vis));
function<void(int)> dfs = [&](int i) {
if (vis[i]) {
return;
}
vis[i] = true;
++cnt;
for (int j : rooms[i]) {
dfs(j);
}
};
dfs(0);
return cnt == n;
}
};func canVisitAllRooms(rooms [][]int) bool {
n := len(rooms)
cnt := 0
vis := make([]bool, n)
var dfs func(int)
dfs = func(i int) {
if vis[i] {
return
}
vis[i] = true
cnt++
for _, j := range rooms[i] {
dfs(j)
}
}
dfs(0)
return cnt == n
}function canVisitAllRooms(rooms: number[][]): boolean {
const n = rooms.length;
const vis: boolean[] = Array(n).fill(false);
const dfs = (i: number) => {
if (vis[i]) {
return;
}
vis[i] = true;
for (const j of rooms[i]) {
dfs(j);
}
};
dfs(0);
return vis.every(v => v);
}impl Solution {
pub fn can_visit_all_rooms(rooms: Vec<Vec<i32>>) -> bool {
let n = rooms.len();
let mut is_open = vec![false; n];
let mut keys = vec![0];
while !keys.is_empty() {
let i = keys.pop().unwrap();
if is_open[i] {
continue;
}
is_open[i] = true;
rooms[i].iter().for_each(|&key| keys.push(key as usize));
}
is_open.iter().all(|&v| v)
}
}我们也可以使用广度优先搜索的方法遍历整张图，用一个哈希表或者数组 vis 标记当前节点是否访问过，以防止重复访问。
具体地，我们定义一个队列
最后统计访问过的节点个数，若与节点总数相同则说明可以访问所有节点，否则说明存在无法到达的节点。
时间复杂度
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
vis = set()
q = deque([0])
while q:
i = q.popleft()
if i in vis:
continue
vis.add(i)
q.extend(j for j in rooms[i])
return len(vis) == len(rooms)class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
int n = rooms.size();
boolean[] vis = new boolean[n];
Deque<Integer> q = new ArrayDeque<>();
q.offer(0);
int cnt = 0;
while (!q.isEmpty()) {
int i = q.poll();
if (vis[i]) {
continue;
}
vis[i] = true;
++cnt;
for (int j : rooms.get(i)) {
q.offer(j);
}
}
return cnt == n;
}
}class Solution {
public:
bool canVisitAllRooms(vector<vector<int>>& rooms) {
int n = rooms.size();
vector<bool> vis(n);
queue<int> q{{0}};
int cnt = 0;
while (q.size()) {
int i = q.front();
q.pop();
if (vis[i]) {
continue;
}
vis[i] = true;
++cnt;
for (int j : rooms[i]) {
q.push(j);
}
}
return cnt == n;
}
};func canVisitAllRooms(rooms [][]int) bool {
n := len(rooms)
vis := make([]bool, n)
cnt := 0
q := []int{0}
for len(q) > 0 {
i := q[0]
q = q[1:]
if vis[i] {
continue
}
vis[i] = true
cnt++
for _, j := range rooms[i] {
q = append(q, j)
}
}
return cnt == n
}function canVisitAllRooms(rooms: number[][]): boolean {
const vis = new Set<number>();
const q: number[] = [0];
while (q.length) {
const i = q.pop()!;
if (vis.has(i)) {
continue;
}
vis.add(i);
q.push(...rooms[i]);
}
return vis.size == rooms.length;
}