【算法与数据结构】841、LeetCode钥匙和房间

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

二、解法

  思路分析：之前的岛屿问题可以看做是无向图，因为所有连接陆地都是互通的。而本题是一个有向图，即使节点之间是连接的，也未必能进入所有的房间。以[[5], [], [1, 3], [5]]为例，从0房间开始出发，到了5房间以后哪里也去不了。因此本是一个有向图全路径搜索的问题，可以用深搜或广搜来解决。

  程序如下：

class Solution {
private:
void dfs(vector<vector<int>>& rooms, vector<bool>& visitRooms, int key) {// 1、递归输入参数
// 2、递归终止条件 访问过的节点直接返回
if (visitRooms[key]) return;
// 3、单层递归逻辑
visitRooms[key] = true;
for (int i = 0; i < rooms[key].size(); i++) {
dfs(rooms, visitRooms, rooms[key][i]);
}
}
public:
bool canVisitAllRooms(vector<vector<int>>& rooms) {
vector<bool> visitRooms = vector<bool>(rooms.size(), false);
dfs(rooms, visitRooms, 0);
for (int i = 0; i < visitRooms.size(); i++) {
if (!visitRooms[i]) return false;
}
return true;
}
};

复杂度分析：

• 时间复杂度：$O(n+m)$，其中$n$是房间的数量，$m$是所有房间中的钥匙数量的总数。
• 空间复杂度：$O(n)$，主要为栈的开销。

三、完整代码

# include <iostream>
# include <vector>
using namespace std;

class Solution {
private:
void dfs(vector<vector<int>>& rooms, vector<bool>& visitRooms, int key) {// 1、递归输入参数
// 2、递归终止条件 访问过的节点直接返回
if (visitRooms[key]) return;
// 3、单层递归逻辑
visitRooms[key] = true;
for (int i = 0; i < rooms[key].size(); i++) {
dfs(rooms, visitRooms, rooms[key][i]);
}
}
public:
bool canVisitAllRooms(vector<vector<int>>& rooms) {
vector<bool> visitRooms = vector<bool>(rooms.size(), false);
dfs(rooms, visitRooms, 0);
for (int i = 0; i < visitRooms.size(); i++) {
if (!visitRooms[i]) return false;
}
return true;
}
};

int main() {
vector<vector<int>> rooms = { {1}, {2}, {3}, {} };
vector<vector<int>> rooms = { {1, 3}, {3, 0, 1}, {2}, {0} };
//vector<vector<int>> rooms = { {2, 3}, {}, {2}, {1, 3} };
Solution s1;
int result = s1.canVisitAllRooms(rooms);
cout << result << endl;
system("pause");
return 0;
}

end

原文地址：https://blog.csdn.net/qq_45765437/article/details/136242614

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！