php+mysql网站开发技术与典型案例导航【源代码】,建设工程抗震管理条例,长沙的科技公司,汕头网站建设策划841. 钥匙和房间 - 力扣#xff08;LeetCode#xff09;
有 n 个房间#xff0c;房间按从 0 到 n - 1 编号。最初#xff0c;除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而#xff0c;你不能在没有获得钥匙的时候进入锁住的房间。当你进入一个房…841. 钥匙和房间 - 力扣LeetCode
有 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 号房间。 1图的深度优先遍历
思路使用深度优先搜索的方式遍历整张图统计可以到达的节点个数并利用数组 visit 记录当前节点是否访问过避免重复访问
class Solution {
public:vectorbool visit;int visCount0;void dfs(vectorvectorint rooms,int roomId){visit[roomId] true;visCount;for(auto roomKey:rooms[roomId]) {if(!visit[roomKey]) {dfs(rooms,roomKey);}}}bool canVisitAllRooms(vectorvectorint rooms) {int n rooms.size();// 房间个数visit.resize(n);dfs(rooms,0);return visCount n;}
};
分析复杂度
时间复杂度O(nm)其中 n 是房间的数量m 是所有房间中的钥匙数量的总数空间复杂度O(n)其中 n 是房间的数量主要为栈的开销
2图的广度优先遍历
思路使用广度优先搜索的方式遍历整张图统计可以到达的节点个数并利用数组 visit 记录当前节点是否访问过避免重复访问 class Solution {
public:bool canVisitAllRooms(vectorvectorint rooms) {int n rooms.size(),visCount0;vectorbool visit(n,0);visit[0]true;queueint Q;Q.emplace(0);while(!Q.empty()) {int roomId Q.front();Q.pop();visCount;for(auto roomKey : rooms[roomId]) {if(!visit[roomKey]) {visit[roomKey] true;Q.emplace(roomKey);}} }return visCountn;}
};
分析复杂度
时间复杂度O(nm)其中 n 是房间的数量m 是所有房间中的钥匙数量的总数空间复杂度O(n)其中 n 是房间的数量主要为队列的开销
推荐和参考文章
841. 钥匙和房间 - 力扣LeetCodehttps://leetcode.cn/problems/keys-and-rooms/solutions/395157/shou-hua-tu-jie-you-xiang-tu-de-bian-li-yi-jing-ge/841. 钥匙和房间 - 力扣LeetCodehttps://leetcode.cn/problems/keys-and-rooms/solutions/393524/yao-chi-he-fang-jian-by-leetcode-solution/
