? 841. 鑰匙和房間

難度：中等

有 n 個(gè)房間，房間按從 0 到 n - 1 編號。最初，除 0 號房間外的其余所有房間都被鎖住。你的目標(biāo)是進(jìn)入所有的房間。然而，你不能在沒有獲得鑰匙的時(shí)候進(jìn)入鎖住的房間。

當(dāng)你進(jìn)入一個(gè)房間，你可能會在里面找到一套不同的鑰匙，每把鑰匙上都有對應(yīng)的房間號，即表示鑰匙可以打開的房間。你可以拿上所有鑰匙去解鎖其他房間。

給你一個(gè)數(shù)組 rooms 其中 rooms[i] 是你進(jìn)入 i 號房間可以獲得的鑰匙集合。如果能進(jìn)入 所有 房間返回 true，否則返回 false。

示例 1：

輸入：rooms = [[1],[2],[3],[]]
輸出：true
解釋：
我們從 0 號房間開始，拿到鑰匙 1。
之后我們?nèi)?1 號房間，拿到鑰匙 2。
然后我們?nèi)?2 號房間，拿到鑰匙 3。
最后我們?nèi)チ?3 號房間。
由于我們能夠進(jìn)入每個(gè)房間，我們返回 true。

示例 2：

輸入：rooms = [[1,3],[3,0,1],[2],[0]]
輸出：false
解釋：我們不能進(jìn)入 2 號房間。

提示：

• $n==rooms.length$
• $2<=n<=1000$
• $0<=rooms[i].length<=1000$
• $1<=sum(rooms[i].length)<=3000$
• $0<=rooms[i][j]<n$
  所有 $rooms[i]$ 的值 互不相同

??思路：

可以將每個(gè)房間當(dāng)作圖中的結(jié)點(diǎn)，鑰匙當(dāng)作圖中的邊，只要所有結(jié)點(diǎn)能夠連通，則返回true;

法一：BFS

數(shù)組 rooms 的長度即為 房間的總個(gè)數(shù)：(bfs)

• 可以設(shè)置一個(gè)數(shù)組 open，記錄是否找到鑰匙；
• 以及一個(gè)隊(duì)列 keys，存儲在每個(gè)房間取得的鑰匙;
• 再另設(shè)一個(gè)變量 count 記錄已打開房間的個(gè)數(shù)，最后只需比較 count 是否等于房間的總個(gè)數(shù)。

法二：DFS

我們可以使用深度優(yōu)先搜索的方式遍歷整張圖，

統(tǒng)計(jì)可以到達(dá)的節(jié)點(diǎn)個(gè)數(shù)，并利用數(shù)組 open 標(biāo)記當(dāng)前節(jié)點(diǎn)是否訪問過，以防止重復(fù)訪問。

??代碼：(C++、Java)

法一：BFS
C++

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        queue<int> keys;
        vector<int> open(rooms.size());
        open[0] = 1;
        int count = 1;
        for(int k : rooms[0]){
            keys.push(k);
        }
        while(!keys.empty()){
            int key = keys.front();
            keys.pop();
            if(open[key] == 0){
                for(int k : rooms[key]){
                    keys.push(k);
                }
                open[key] = 1;
                count++;
            }
        }
        return count == rooms.size();
    }
};

Java

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        Queue<Integer> keys = new LinkedList();
        int[] open = new int[rooms.size()];
        open[0] = 1;
        int count = 1;
        for(int k : rooms.get(0)){
            keys.offer(k);
        }
        while(!keys.isEmpty()){
            int key = keys.poll();
            if(open[key] == 0){
                for(int k : rooms.get(key)){
                    keys.offer(k);
                }
                open[key] = 1;
                count++;
            }
        }
        return count == rooms.size();
    }
}

法二：DFS
C++

class Solution {
private:
    void dfs(const vector<vector<int>>& rooms, int key, vector<int>& open){
        if(open[key] == 1) return;
        open[key] = 1;
        for(int k : rooms[key]){
            dfs(rooms, k, open);
        }
    }
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        vector<int> open(rooms.size());
        dfs(rooms, 0, open);
        for(int p : open){
            if(p == 0) return false;
        }
        return true;
    }
};

Java

class Solution {
    private void dfs(List<List<Integer>> rooms, int key, int[] open){
        if(open[key] == 1) return;
        open[key] = 1;
        for(int k : rooms.get(key)){
            dfs(rooms, k, open);
        }
    }
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int[] open = new int[rooms.size()];
        dfs(rooms, 0, open);
        for(int p : open){
            if(p == 0) return false;
        }
        return true;
    }
}

?? 運(yùn)行結(jié)果：

?? 復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(n+m)$，其中 n 為房間的數(shù)量，m 是所有房間中的鑰匙數(shù)量的總數(shù)。
• 空間復(fù)雜度：$O(n)$，主要為隊(duì)列（bfs）或棧空間（dfs）的開銷。

題目來源：力扣。

放棄一件事很容易，每天能堅(jiān)持一件事一定很酷，一起每日一題吧！
關(guān)注我LeetCode主頁 / CSDN—力扣專欄，每日更新！文章來源地址http://www.zghlxwxcb.cn/news/detail-566160.html

注： 如有不足，歡迎指正！

到了這里，關(guān)于(圖論) 841. 鑰匙和房間 ——【Leetcode每日一題】的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！