Skip to content

Latest commit

 

History

History
273 lines (213 loc) · 6.92 KB

0841.钥匙和房间.md

File metadata and controls

273 lines (213 loc) · 6.92 KB
Raw

参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

841.钥匙和房间

力扣题目链接

有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。

在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，...，N-1] 中的一个整数表示，其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。

最初，除 0 号房间外的其余所有房间都被锁住。

你可以自由地在房间之间来回走动。

如果能进入每个房间返回 true，否则返回 false。

示例 1：

  • 输入: [[1],[2],[3],[]]
  • 输出: true
  • 解释: 我们从 0 号房间开始，拿到钥匙 1。 之后我们去 1 号房间，拿到钥匙 2。 然后我们去 2 号房间，拿到钥匙 3。 最后我们去了 3 号房间。 由于我们能够进入每个房间，我们返回 true。

示例 2：

  • 输入：[[1,3],[3,0,1],[2],[0]]
  • 输出：false
  • 解释：我们不能进入 2 号房间。

思

其实这道题的本质就是判断各个房间所连成的有向图，说明不用访问所有的房间。

如图所示：

示例1就可以访问所有的房间，因为通过房间里的key将房间连在了一起。

示例2中，就不能访问所有房间，从图中就可以看出，房间2是一个孤岛，我们从0出发，无论怎么遍历，都访问不到房间2。

认清本质问题之后，使用 广度优先搜索(BFS) 还是 深度优先搜索(DFS) 都是可以的。

BFS C++代码代码如下：

class Solution {
bool bfs(const vector<vector<int>>& rooms) {
    vector<int> visited(rooms.size(), 0); // 标记房间是否被访问过
    visited[0] = 1; //  0 号房间开始
    queue<int> que;
    que.push(0); //  0 号房间开始

    // 广度优先搜索的过程
    while (!que.empty()) {
        int key = que.front(); que.pop();
         vector<int> keys = rooms[key];
         for (int key : keys) {
             if (!visited[key]) {
                 que.push(key);
                 visited[key] = 1;
             }
         }
    }
    // 检查房间是不是都遍历过了
    for (int i : visited) {
        if (i == 0) return false;
    }
    return true;

}
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        return bfs(rooms);
    }
};

DFS C++代码如下：

class Solution {
private:
    void dfs(int key, const vector<vector<int>>& rooms, vector<int>& visited) {
        if (visited[key]) {
            return;
        }
        visited[key] = 1;
        vector<int> keys = rooms[key];
        for (int key : keys) {
            // 深度优先搜索遍历
            dfs(key, rooms, visited);
        }
    }
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        vector<int> visited(rooms.size(), 0);
        dfs(0, rooms, visited);
        //检查是否都访问到了
        for (int i : visited) {
            if (i == 0) return false;
        }
        return true;
    }
};

其他语言版本

Java：

class Solution {
     private void dfs(int key, List<List<Integer>>  rooms, List<Boolean> visited) {
        if (visited.get(key)) {
            return;
        }

        visited.set(key, true);
        for (int k : rooms.get(key)) {
            // 深度优先搜索遍历
            dfs(k, rooms, visited);
        }
    }


    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        List<Boolean> visited = new ArrayList<Boolean>(){{
            for(int i = 0 ; i < rooms.size(); i++){
                add(false);
            }
        }};

        dfs(0, rooms, visited);

        //检查是否都访问到了
        for (boolean flag : visited) {
            if (!flag) {
                return false;
            }
        }
        return true;
    }
}

Python：

python3

class Solution:

    def dfs(self, key: int, rooms: List[List[int]]  , visited : List[bool] ) :
        if visited[key] :
            return

        visited[key] = True
        keys = rooms[key]
        for i in range(len(keys)) :
            # 深度优先搜索遍历
            self.dfs(keys[i], rooms, visited)

    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited = [False for i in range(len(rooms))]

        self.dfs(0, rooms, visited)

        # 检查是否都访问到了
        for i in range(len(visited)):
            if not visited[i] :
                return False
        return True

Go：

func dfs(key int, rooms [][]int, visited []bool ) {
	if visited[key] {
		return;
	}

	visited[key] = true
	keys := rooms[key]
	for _ , key := range keys {
		// 深度优先搜索遍历
		dfs(key, rooms, visited);
	}
}

func canVisitAllRooms(rooms [][]int) bool {

	visited := make([]bool, len(rooms));

	dfs(0, rooms, visited);

	//检查是否都访问到了
	for i := 0; i < len(visited); i++ {
		if !visited[i] {
			return false;
		}
	}
	return true;
}

JavaScript：

//DFS
var canVisitAllRooms = function(rooms) {
    const dfs = (key, rooms, visited) => {
        if(visited[key]) return;
        visited[key] = 1;
        for(let k of rooms[key]){
            // 深度优先搜索遍历
            dfs(k, rooms, visited);
        }
    }
    const visited = new Array(rooms.length).fill(false);
    dfs(0, rooms, visited);
    //检查是否都访问到了
    for (let i of visited) {
        if (!i) {
            return false;
        }
    }
    return true;
};

//BFS
var canVisitAllRooms = function(rooms) {
    const bfs = rooms => {
        const visited = new Array(rooms.length).fill(0); // 标记房间是否被访问过
        visited[0] = 1; // 0 号房间开始
        const queue = []; //js数组作为队列使用
        queue.push(0); //  0 号房间开始
        // 广度优先搜索的过程
        while(queue.length !== 0){
            let key = queue[0];
            queue.shift();
            for(let k of rooms[key]){
                if(!visited[k]){
                    queue.push(k);
                    visited[k] = 1;
                }
            }
        }
        // 检查房间是不是都遍历过了
        for(let i of visited){
            if(i === 0) return false;
        }
        return true;
    }
    return bfs(rooms);
};