841. 钥匙和房间
2023-02-18 16:34:33 时间
841. 钥匙和房间
方法一:深度优先搜索
思路及解法
我们可以使用深度优先搜索的方式遍历整张图,统计可以到达的节点个数,并利用数组 vis 标记当前节点是否访问过,以防止重复访问。
class Solution {
public:
vector<int> vis;
int num;
void dfs(vector<vector<int> >& rooms, int x) {
vis[x] = true;
num++;
for (int i = 0; i < rooms[x].size(); i++)
if (!vis[rooms[x][i]])
dfs(rooms, rooms[x][i]);
}
bool canVisitAllRooms(vector<vector<int> >& rooms) {
int n = rooms.size();
num = 0;
vis.resize(n);
dfs(rooms, 0);
return num == n;
}
};
复杂度分析
时间复杂度:O(n+m),其中 n 是房间的数量,m 是所有房间中的钥匙数量的总数。
空间复杂度:O(n),其中 n是房间的数量。主要为栈空间的开销。
方法二:广度优先搜索
思路及解法
我们也可以使用广度优先搜索的方式遍历整张图,统计可以到达的节点个数,并利用数组vis 标记当前节点是否访问过,以防止重复访问。
class Solution {
public:
bool canVisitAllRooms(vector<vector<int> >& rooms) {
int n=rooms.size();
int num=0;
queue<int>que;
que.push(0);
vector<bool>vis(n);
vis[0]=true;
while (!que.empty())
{
int front = que.front();
que.pop();
num++;
for (int i = 0; i < rooms[front].size(); i++)
{
if(!vis[rooms[front][i]]){
que.push(rooms[front][i]);
vis[rooms[front][i]]=true;
}
}
}
return num==n;
}
};
复杂度分析
时间复杂度:O(n+m),其中 n 是房间的数量,m 是所有房间中的钥匙数量的总数。
空间复杂度:O(n),其中 n是房间的数量。主要为栈空间的开销。
相关文章
- [PHP] 持续交付Jenkins安装
- [PHP] PHP调用IMAP协议读取邮件类库
- [PHP] 现代化PHP之路:composer的镜像站设置
- [PHP] 现代化PHP之路:composer的安装和升级
- [PHP] 内部接口简单加密验证方式
- [MySQL] mysql地理位置服务geometry字段类型
- [PHP] 深度解析Nginx下的PHP框架路由实现
- [PHP] 项目实践中的自动加载实现
- [PHP] 项目实践中使用的IOC容器思想
- [Nginx] 博客园出现了502错误该怎么追查原因
- [MySQL] myisam比innodb查询过程效率探究
- [MySQL]myisam表的索引结构以及查询过程
- [MySQL] innodb表为varchar字段建立索引后的查询过程
- [MySQL] 联合索引最左前缀原则的原因
- [日常] 浏览器前进后退与数据结构的思想
- [PHP] 判断两个数组是否相同
- [TCP/IP] HTTPS的工作原理
- [TCP/IP] SSL的通讯原理
- [PHP] 使用strace排查接口响应速度慢过程
- [TCP/IP] TCP流和UDP数据报之间的区别