建设网站的和服务器,有哪些网站可以做店面设计,国外优秀网站建设,做企业官网教程总结leetcode75中的图深度优先搜索算法题解题思路。 上一篇#xff1a;力扣75——二叉搜索树 力扣75——图深度优先搜索 1 钥匙和房间2 省份数量3 重新规划路线4 除法求值1-4 解题总结 1 钥匙和房间
题目#xff1a;
有 n 个房间#xff0c;房间按从 0 到 n - 1 编号。最初…总结leetcode75中的图深度优先搜索算法题解题思路。 上一篇力扣75——二叉搜索树 力扣75——图深度优先搜索 1 钥匙和房间2 省份数量3 重新规划路线4 除法求值1-4 解题总结 1 钥匙和房间
题目
有 n 个房间房间按从 0 到 n - 1 编号。最初除 0 号房间外的其余所有房间都被锁住。
你的目标是进入所有的房间。然而你不能在没有获得钥匙的时候进入锁住的房间。当你进入一个房间你可能会在里面找到一套不同的钥匙每把钥匙上都有对应的房间号
即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入
所有 房间返回 true否则返回 false。题解 我的方法广度优先搜索。进入一个房间t拿到里面的钥匙tmp然后把钥匙tmp压入队列q中。while循环从队列q拿钥匙直到q空了为止。最后检查所有房间visit是否都被访问。 官方代码深度优先搜索。利用递归函数dfs进入一个房间拿到钥匙再用for循环调用dfs函数。
class Solution {
public:bool canVisitAllRooms(vectorvectorint rooms) {int numRooms rooms.size();vectorint visit(numRooms,0);visit[0] 1;vectorint tmp;queueint q;q.push(0);while (!q.empty()) {tmp rooms[q.front()];q.pop();if (!tmp.empty()) {for (int t : tmp) {if (visit[t] 1)continue;q.push(t);visit[t] 1;}}}for (int v : visit) {if (v 0) return false;}return true;}
};
//官方的代码更简洁合理
/*
class Solution {
public:vectorint vis;int num;void dfs(vectorvectorint rooms, int x) {vis[x] true;num;for (auto it : rooms[x]) {if (!vis[it]) {dfs(rooms, it);}}}bool canVisitAllRooms(vectorvectorint rooms) {int n rooms.size();num 0;vis.resize(n);dfs(rooms, 0);return num n;}
};
*/2 省份数量
题目
有 n 个城市其中一些彼此相连另一些没有相连。如果城市 a 与城市 b 直接相连
且城市 b 与城市 c 直接相连那么城市 a 与城市 c 间接相连。省份 是一组直接或间接相连的城市组内不含其他没有相连的城市。给你一个 n x n 的矩阵 isConnected 其中 isConnected[i][j] 1 表示第 i 个城市和
第 j 个城市直接相连而 isConnected[i][j] 0 表示二者不直接相连。返回矩阵中 省份 的数量。题解 深度优先搜索。for遍历每个城市用递归函数dfs找到所有与当前城市i直接或间接相连的城市用visit来标记已经搜索过的城市。
class Solution {
public:int findCircleNum(vectorvectorint isConnected) {int nums 0, nC isConnected.size();vectorint visit(nC, 0);for (int i 0; i nC; i) {if (visit[i] 0) {nums;dfs(isConnected, visit, i);}}return nums;}void dfs(vectorvectorint isConnected,vectorint visit,int i) {visit[i] 1;for (int j 0; j isConnected.size(); j) {if (isConnected[i][j] 1 visit[j] 0) {dfs(isConnected, visit, j);}}}
};3 重新规划路线
题目
n 座城市从 0 到 n-1 编号其间共有 n-1 条路线。因此要想在两座不同城市之间旅行只有
唯一一条路线可供选择路线网形成一颗树。去年交通运输部决定重新规划路线以改变交通
拥堵的状况。路线用 connections 表示其中 connections[i] [a, b] 表示从城市 a 到 b 的一条有向
路线。今年城市 0 将会举办一场大型比赛很多游客都想前往城市 0 。
请你帮助重新规划路线方向使每个城市都可以访问城市 0 。返回需要变更方向的最小路线数。
题目数据 保证 每个城市在重新规划路线方向后都能到达城市 0 。题解 广度优先搜索。目的是将所有路线的方向都朝着城市0所以遍历所有与城市0直接相连的城市然后对这每一个相连的城市进行广度优先搜索更改那些方向错误的路线。具体的过程在代码中有注释。
class Solution {
public:int minReorder(int n, vectorvectorint connections) {vectorvectorint conn_idx(n, vectorint());//这里使用了类似于邻接表的方法将和节点有关的连接的id序号加入到对应的向量中//这样在后面遍历的时候只要查找connections里面对应的id即可//要注意这里连接两端都加入了连接的序号for (int i 0; i connections.size(); i) {conn_idx[connections[i][0]].push_back(i);conn_idx[connections[i][1]].push_back(i);}vectorbool vi(connections.size(), false);//此处标志的是某条边是否被访问过而不是某个点是否被访问过int ans 0;queueint que;que.push(0);while (!que.empty()) {auto q que.front();que.pop();//这个循环是对和节点q相关的连接进行遍历通过上面存储的连接的id进行遍历for (auto idx : conn_idx[q]) {if (vi[idx]) continue;vi[idx] true;int a connections[idx][0];//连接的起始int b connections[idx][1];//连接的终点ans (a q);//如果当前点是出的那么要修改为入ansa (a q) ? b : a;que.push(a);}}return ans;}
};4 除法求值
题目
给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件其中 equations[i] [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi values[i] 。每个 Ai 或 Bi 是一个表示
单个变量的字符串。
另有一些以数组 queries 表示的问题其中 queries[j] [Cj, Dj] 表示第 j 个问题请你根
据已知条件找出 Cj / Dj ? 的结果作为答案。返回 所有问题的答案 。如果存在某个无法确定的答案则用 -1.0 替代这个答案。如果问题中出现
了给定的已知条件中没有出现的字符串也需要用 -1.0 替代这个答案。注意输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况且不存在任何矛盾的结果。
注意未在等式列表中出现的变量是未定义的因此无法确定它们的答案。题解 并查集。 1 先定义1个unordered_map类型的parent它记录了一个数的被除数被除数的被除数是它自己。 2 再定义1个unordered_map类型的mp记录1个数除被除数得到的值。 3 接着定义函数find()该函数可以找到一个数的祖先。在这个过程中如果发现一个数的祖先跟它隔了2代或更多代就递归进行压缩并修改对应的mp值。 4 然后通过for循环遍历equations将所以除法公式及其结果记录好。 5 最后计算queries中的问题。如果被除数或除数不存在于parent中则无法求解如果除数和被除数的祖先不是同一个也无法求解如果除数和被除数是同一个祖先则直接用它们的mp值做除法即可。
class Solution {
public:unordered_mapstring, string parent;unordered_mapstring, double mp;string find(string x){if(parent[x] x) return x;string px parent[x];string res parent[x] find(parent[x]); mp[x] * mp[px];return res;}vectordouble calcEquation(vectorvectorstring equations, vectordouble values, vectorvectorstring queries) {int n equations.size();for(int i 0; i n; i ){string a equations[i][0], b equations[i][1];double v values[i];if(parent.find(a) parent.end() parent.find(b) parent.end()){parent[a] a; parent[b] a;mp[b] v, mp[a] 1.0;}else if(parent.find(a) parent.end()){parent[a] a; string pb find(b);mp[a] 1.0;mp[pb] v / mp[b];parent[pb] a;}else if(parent.find(b) parent.end()){parent[b] a;mp[b] v;}else{string pa find(a), pb find(b);if(pa pb) continue;parent[pb] pa;mp[pb] mp[a] * v / mp[b];} }vectordouble res;for(auto item : queries){string a item[0], b item[1];if(parent.find(a) parent.end() || parent.find(b) parent.end()) res.push_back(-1.0);else{string pa find(a), pb find(b);if(pa ! pb) res.push_back(-1.0);else res.push_back(mp[b] / mp[a]);}}return res;}
};1-4 解题总结
a 题目类型总结
题目1从1个节点出发是否可以到达所有节点。题目2所有节点构成几个连通域。题目3从任意节点出发是否可以到达某个节点。题目4节点1是否可以到达节点2。
b 题目1和题目3本质上是一样的只是边的方向相反了而已。他们既可以使用深度优先搜索也可以使用广度优先搜索。 c 题目2既可以使用深度优先搜索也可以使用广度优先搜索。 d 题目4是检查两个点之间是否连通所以用深度优先搜索更合适。 e 这些题目不限制是否会重复经过某个节点只考虑哪些节点是相通的。
