建行打95533能改密码吗,山东济南网站建设优化,网站建设设计多少钱,柳市网站设计推广文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析#xff1a;之前的岛屿问题可以看做是无向图#xff0c;因为所有连接陆地都是互通的。而本题是一个有向图#x… 文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析之前的岛屿问题可以看做是无向图因为所有连接陆地都是互通的。而本题是一个有向图即使节点之间是连接的也未必能进入所有的房间。以[[5], [], [1, 3], [5]]为例从0房间开始出发到了5房间以后哪里也去不了。因此本是一个有向图全路径搜索的问题可以用深搜或广搜来解决。 程序如下
class Solution {
private:void dfs(vectorvectorint rooms, vectorbool 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(vectorvectorint rooms) {vectorbool visitRooms vectorbool(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 ) O(nm) O(nm)其中 n n n是房间的数量 m m m是所有房间中的钥匙数量的总数。空间复杂度 O ( n ) O(n) O(n)主要为栈的开销。
三、完整代码
# include iostream
# include vector
using namespace std;class Solution {
private:void dfs(vectorvectorint rooms, vectorbool 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(vectorvectorint rooms) {vectorbool visitRooms vectorbool(rooms.size(), false);dfs(rooms, visitRooms, 0);for (int i 0; i visitRooms.size(); i) {if (!visitRooms[i]) return false;}return true;}
};int main() {vectorvectorint rooms { {1}, {2}, {3}, {} };vectorvectorint rooms { {1, 3}, {3, 0, 1}, {2}, {0} };//vectorvectorint rooms { {2, 3}, {}, {2}, {1, 3} };Solution s1;int result s1.canVisitAllRooms(rooms);cout result endl;system(pause);return 0;
}end
