精品网站建,城乡厅建设部网站,响应式网站的尺寸,代账公司网站模板目录
1.BFS 2.树里的宽搜
题目一——429. N 叉树的层序遍历 - 力扣#xff08;LeetCode#xff09; 题目二——103. 二叉树的锯齿形层序遍历 - 力扣#xff08;LeetCode#xff09;
题目三——662. 二叉树最大宽度 - 力扣#xff08;LeetCode#xff09;
题目四——…目录
1.BFS 2.树里的宽搜
题目一——429. N 叉树的层序遍历 - 力扣LeetCode 题目二——103. 二叉树的锯齿形层序遍历 - 力扣LeetCode
题目三——662. 二叉树最大宽度 - 力扣LeetCode
题目四——515. 在每个树行中找最大值 - 力扣LeetCode
3.BFS解决最短路径问题
为什么BFS可以解决最短路径问题
题目一——1926. 迷宫中离入口最近的出口 - 力扣LeetCode
题目二——433. 最小基因变化 - 力扣LeetCode 题目三——127. 单词接龙 - 力扣LeetCode
题目四——675. 为高尔夫比赛砍树 - 力扣LeetCode
4.多源BFS
题目一——542. 01 矩阵 - 力扣LeetCode
题目二——1020. 飞地的数量 - 力扣LeetCode
题目三—— 1765. 地图中的最高点 - 力扣LeetCode
题目四—— 1162. 地图分析 - 力扣LeetCode 5.BFS解决拓扑排序
题目一——207. 课程表 - 力扣LeetCode
题目二——210. 课程表 II - 力扣LeetCode 1.BFS
BFS 全称是 Breadth First Search中文名是宽度优先搜索也叫广度优先搜索。
是图上最基础、最重要的搜索算法之一。
所谓宽度优先。就是每次都尝试访问同一层的节点。 如果同一层都访问完了再访问下一层。
BFS广度优先搜索在处理问题时优先考虑更多的机会而不是像DFS那样优先走一条路再回溯
BFS基于队列实现目的是把可能的解放在同一层处理即BFS队列中至多只有两层的解
考虑完前一层可能的解后再考虑下一层的解。把当前解的后续解再放到队列尾部。 BFS是基于队列实现的 如上图中BCDE处在同一层考虑那么
考虑到 B 的后续解FGH时先把B弹出队列再把FGH 放在 CDE 后面即CDEFGH 。考虑到 C 的后续解IJ时先把C弹出队列再把 IJ 放在 DEFGH 后面即 DEFGHIJ 。考虑到 D 的后续解K时先把D弹出队列再把 K 放在 EFGHIJ 后面即 EFGHIJK 。考虑到 E 的后续解这里没有时先把E弹出队列再把这里就不需要放在 FGHIJK 后面了即 FGHIJK 。 现在队列里面只剩下第三层的了这样子我们可以一直按照上面这个逻辑执行下去直到队列为空 下面结合一个图 (graph) 的实例说明 BFS 的工作过程和原理
1将起始节点1放入队列中标记为已遍历 2从queue中取出队列头的节点1找出与节点1邻接的节点2,3标记为已遍历然后放入queue中。 3从queue中取出队列头的节点2找出与节点2邻接的节点1,4,5由于节点1已遍历排除标记4,5为已遍历然后放入queue中。 4从queue中取出队列头的节点3找出与节点3邻接的节点1,6,7由于节点1已遍历排除标记6,7为已遍历然后放入queue中。 5从queue中取出队列头的节点4找出与节点4邻接的节点2,82属于已遍历点排除因此标记节点8为已遍历然后放入queue中。 6从queue中取出队列头的节点5找出与节点5邻接的节点2,82,8均属于已遍历点不作下一步操作。 7从queue中取出队列头的节点6找出与节点6邻接的节点3,8,93,8属于已遍历点排除因此标记节点9为已遍历然后放入queue中。 8从queue中取出队列头的节点7找出与节点7邻接的节点3, 93,9属于已遍历点不作下一步操作。 9从queue中取出队列头的节点8找出与节点8邻接的节点4,5,64,5,6属于已遍历点不作下一步操作。 10从queue中取出队列头的节点9找出与节点9邻接的节点6,76,7属于已遍历点不作下一步操作。 11queue 为空则遍历结束 2.树里的宽搜
我们看一下怎么使用BFS遍历树
如下动图所示 下面解释一下整个 BFS 的过程我们整个遍历的过程是这样的
1、将节点 A 加入到队列 q 中。此时队列只有一个结点 A。
2、队列 q 不为空我们弹出队列的首节点也就是 A找到 A 的所有邻接节点。从上图可以看出也就是 B、C、D我们将 B、C、D 加入到队列中。这样队列内的元素就是 B,C,D。
3、队列 q 不为空我们弹出队列的首节点也就是 B找到 B 的所有邻接节点。从上图可以看出也就是 E、F我们将 E、F 加入到队列中。这样队列内的元素就是 C,D,E,F。
4、队列 q 不为空我们弹出队列的首节点也就是 C找到 C 的所有邻接节点。从上图可以看出C 没有邻接节点。这样队列内的元素就是 D,E,F。
5、队列 q 不为空我们弹出队列的首节点也就是 D找到 D 的所有邻接节点。从上图可以看出也就是 H、I、J我们将 H、I、J 加入到队列中。这样队列内的元素就是 E,F,H,I,J。
6、队列 q 不为空我们弹出队列的首节点也就是 E找到 E 的所有邻接节点。从上图可以看出C 没有邻接节点。这样队列内的元素就是 F,H,I,J。
7、队列 q 不为空我们弹出队列的首节点也就是 F找到 F 的所有邻接节点。从上图可以看出F 没有邻接节点。这样队列内的元素就是 H,I,J。
8、队列 q 不为空我们弹出队列的首节点也就是 H找到 H 的所有邻接节点。从上图可以看出也就是 K我们将 K 加入到队列中。这样队列内的元素就是 I,J,K。
9、队列 q 不为空我们弹出队列的首节点也就是 I找到 I 的所有邻接节点。从上图可以看出也就是 G、L我们将 G、L 加入到队列中。这样队列内的元素就是 I,J,K,G,L。
10、队列 q 不为空我们弹出队列的首节点也就是 I找到 I 的所有邻接节点。从上图可以看出I 没有邻接节点。这样队列内的元素就是 J,K,G,L。
11、队列 q 不为空我们弹出队列的首节点也就是 J找到 J 的所有邻接节点。从上图可以看出J 没有邻接节点。这样队列内的元素就是 K,G,L。
12、队列 q 不为空我们弹出队列的首节点也就是 K找到 K 的所有邻接节点。从上图可以看出K 没有邻接节点。这样队列内的元素就是 G,L。
13、队列 q 不为空我们弹出队列的首节点也就是 G。从上图可以看出G 没有邻接节点。这样队列内的元素就是 L。
14、队列 q 不为空我们弹出队列的首节点也就是 L。从上图可以看出L 没有邻接节点。这样队列内就没有元素结束。
题目一——429. N 叉树的层序遍历 - 力扣LeetCode 这个题目的意思是相当简单易懂的吧。
有人可能好奇为什么层序遍历需要借助队列这个数据结构呢
我们看下面这个图就明白了 额这个不是和那个队列的先进先出的性质是一模一样的吗所以我们就借助队列来解决这种问题。
我们先搞一个队列如果根节点不为空我们让根节点入队列接下来是一个while循环当队列不为空的时候一直执行下面这个先把队头元素从队列里删除把队头元素的孩子入队。直到这个队列为空为止这个层序遍历就算是结束了。
我们现在来考虑一下我们怎么分层呢
我们其实可以另外设置一个变量先统计队列有多少个元素有多少的元素我们就先出队多少次。这个时候队列里就只剩孩子结点了即下一层的然后我们重复上面这个步骤就好了。
我们很快就能写出下面这个代码啊
class Solution {
public:vectorvectorint levelOrder(Node* root) {vectorvectorintret;//记录最终结果queueNode*q;if(rootnullptr){return ret;}q.push(root);//将根结点添加进队列里面while(q.size()!0){vectorinttmp;//统计本层的元素int sq.size();//记录当前队列里面的元素个数//先把队列里所有结点的孩子结点加入到队列里面for(int i0;is;i){Node* tq.front();//获取队列第一个元素q.pop();//删除队列第一个元素tmp.push_back(t-val);//将队列第一个元素的值添加进tmp里面//将第一个元素的孩子结点添加进队列里面//注意孩子结点是以数组的方式访问的for(Node* child:t-children){if(child!nullptr){q.push(child);}}}ret.push_back(tmp);//将本层的结果集添加进总的结果里面}return ret;}
}; 题目二——103. 二叉树的锯齿形层序遍历 - 力扣LeetCode 这题和上面那题好像差不多只不过就是改变了层序遍历的规则而已。
我们还是使用BFS来解决我们增加一个标记位这个锯齿形遍历就只需要在偶数行将结果逆序一下就好了。
class Solution
{public:vectorvectorint zigzagLevelOrder(TreeNode* root) {vectorvectorintret;//总的结果queueTreeNode* q;//队列if(rootnullptr){return ret;}q.push(root);//将根节点加入到队列里面int level1;//每一行的标记位while(q.size()!0){vectorinttmp;//记录这一行的结果int szq.size();for(int i0;isz;i){TreeNode* fq.front();//获取队列的第一个元素q.pop();//删除队列的第一个元素tmp.push_back(f-val);//将第一个元素添加进这一行的结果集里面if(f-left!nullptr){q.push(f-left);}if(f-right!nullptr){q.push(f-right);}}if(level%20)//偶数行的结果要逆置{reverse(tmp.begin(),tmp.end());}level;//更新标记ret.push_back(tmp);}return ret;}}; 题目三——662. 二叉树最大宽度 - 力扣LeetCode 特别注意这题是要将空结点来当作一个有效的元素的这就让这一题没有那么简单了啊 我们可以利用数组存储二叉树的方式给结点编号大家可以回忆一下堆的实现堆的介绍堆的向下调整算法堆的向上调整算法_堆调整-CSDN博客 对于数组下标为1开始的情况对于给定下标 i 的结点其父结点、左子结点和右子结点的下标可以通过以下关系式计算 下标i元素的左子结点下标2 * i 下标i元素的右子结点下标2 * i 1 还是利⽤层序遍历但是这⼀次队列⾥⾯不单单存结点信息并且还存储当前结点如果在数组中存 储所对应的下标在我们学习数据结构-堆的时候计算左右孩⼦的⽅式。这样我们计算每⼀层宽度的时候⽆需考虑空节点只需将当层结点的左右结点的下标相减再加 。 但是这⾥有个细节问题
如果⼆叉树的层数⾮常恐怖的话我们任何⼀种数据类型都不能存下下标 的值。
但是没有问题因为
我们数据的存储是⼀个环形的结构并且题⽬说明数据的范围在 int 这个类型的最⼤值的范围之内因此不会超出⼀圈
因此如果是求差值的话我们⽆需考虑溢出的情况。
class Solution {
public:// 计算给定二叉树的宽度int widthOfBinaryTree(TreeNode* root) {// 使用数组来模拟一个队列来存储节点和它们的相对位置基于层级的编号// TreeNode* 表示节点unsigned int 表示该节点在其层级中的位置编号从1开始vectorpairTreeNode*, unsigned int q; // 根节点入队位置编号为1q.push_back({root, 1});// 用于存储最宽层的宽度unsigned int ret 0;// 当队列不为空时继续循环while (q.size()) {// 获取当前层最左边和最右边节点的位置编号// x1 和 y1 是当前层最左边的节点及其位置编号// x2 和 y2 是当前层最右边的节点及其位置编号auto [x1, y1] q[0];auto [x2, y2] q.back();// 更新最宽层的宽度为当前层最左边和最右边节点的位置编号之差加1ret max(ret, y2 - y1 1);// 准备下一层的节点入队vectorpairTreeNode*, unsigned int tmp; // 临时队列用于存储下一层的节点// 遍历当前层的所有节点for (auto [x, y] : q){// 如果左子节点存在将其入队位置编号为当前节点位置编号的两倍if (x-left)tmp.push_back({x-left, y * 2});// 如果右子节点存在将其入队位置编号为当前节点位置编号的两倍加一if (x-right)tmp.push_back({x-right, y * 2 1});}// 更新队列为下一层的节点q tmp;}// 返回最宽层的宽度return ret;}
}; 题目四——515. 在每个树行中找最大值 - 力扣LeetCode 这题一点难度也没有
class Solution {
public:vectorint largestValues(TreeNode* root) {vectorint ret;queueTreeNode* q;if (root nullptr) {return ret;}q.push(root);while (q.size() ! 0) {int sz q.size();int tmp INT_MIN;for (int i 0; i sz; i) {TreeNode* f q.front();q.pop();tmp max(tmp, f-val);if (f-left ! nullptr) {q.push(f-left);}if (f-right ! nullptr) {q.push(f-right);}}ret.push_back(tmp);}return ret;}
}; 3.BFS解决最短路径问题
这个最短路径其实是图论的问题但是我们不讨论加权的情况我们只考虑边权相同的情况 最短路径无非就是给你很多点然后问你两个点的最短路径是多少
这个解法特别简单我们只需要从起点开始进行BFS即可。
然后我们需要一个哈希表来记录我们访问过的位置
我们把A放进队列里面然后标记A为已经访问然后看看A能访问哪些点就是B,C把这些点放进队列里面然后标记B,C为可读
然后接着看B能访问哪些点这里是D然后把这个D放到这个队列里面来然后弹出B然后接着看C能访问哪些点这里是E然后把这个E放到这个队列里面来然后弹出C 后面发现D没必要另外拓展了因为肯定比C的长。
……
为什么BFS可以解决最短路径问题
广度优先搜索BFS能够解决最短路径问题尤其是在无权图即图中所有边的权重都相等的情况下。以下是BFS为何适用于解决最短路径问题的几个关键点 层次遍历BFS按照层次或深度遍历图中的节点。它从起始节点开始首先访问所有直接相连的邻居节点然后再访问这些邻居节点的邻居以此类推。这种层次遍历的方式保证了在访问到某个节点时该节点是通过最短路径从起始节点到达的在无权图中。 最短路径性质在无权图中任何节点到起始节点的最短路径都可以通过逐步向外扩展的方式找到。BFS正是按照这种方式进行遍历的因此它能够在找到目标节点时保证是通过最短路径到达的。 队列实现BFS通常使用队列FIFO先进先出来实现。起始节点被放入队列中然后依次处理队列中的节点。对于每个节点它的所有未访问过的邻居节点都会被加入到队列的末尾。这样当队列中的某个节点被处理时它一定是通过最短路径从起始节点到达的因为队列中的节点是按照层次顺序排列的。 避免重复访问为了确保算法的正确性BFS需要跟踪已经访问过的节点以避免重复访问和陷入无限循环。这通常通过一个布尔数组或集合来实现。 为什么使用BFS能解决最短路径问题 因为使用BFS时我们都是让每种情况同时发生保证每种情况每一次行走的步数都是一样的这样子最先到达终点的情况一定是最短路径 如何找到最短路径是多少啊 拓展的层数就是最短路径 题目一——1926. 迷宫中离入口最近的出口 - 力扣LeetCode 为什么使用BFS能解决最短路径问题 因为使用BFS时我们都是让每种情况同时发生每一次行走的步数都是一样的这样子最先到达终点的情况一定是最短路径 我们完全可以假设这个人往上下左右四个方向同时走每一次都走一步这样子最先到达终点的就是最短路径 那我们怎么保证同时走呢 很简单我们还是使用层序遍历的那个思路我们只需要保证每走一步的所有情况都处理完才会去讨论下一步的情况 我怎么知道哪些情况是同一步的啊 我们其实可以另外设置一个变量先统计队列有多少个元素有多少的元素我们就先出队多少次。这个时候队列里就只剩下一步的然后我们重复上面这个步骤就好了。 class Solution {
public:bool check[101][101]{false};int dx[4]{0,0,-1,1};int dy[4]{1,-1,0,0};int nearestExit(vectorvectorchar maze, vectorint entrance) {int ientrance[0],jentrance[1];check[i][j]true;queuepairint,intq;q.push({i,j});int path0;while(q.size()!0){ path;int szq.size();//同一步有多少种情况for(int s0;ssz;s){//处理这一步的情况auto [a,b]q.front();q.pop();//当前这一步处理完才会考虑下一步for(int k0;k4;k){int xadx[k],ybdy[k];if(x0xmaze.size()y0ymaze[0].size()maze[x][y].check[x][y]false){//是否已经到达出口了if(x0||xmaze.size()-1||y0||ymaze[0].size()-1){return path;}q.push({x,y});check[x][y]true;}}}}return -1;}
}; 题目二——433. 最小基因变化 - 力扣LeetCode 这个题目意思算是很简单了吧。 我们可以转换为边权为1的路径问题
我们可以从前往后遍历整个start字符串从第一个位置开始 将它的每个位置都尝试修改成可以修改成的字符如果说修改的字符串出现在bank里面并且这个字符串没有被出现过我们就再次将它添加进这个队列里面 如果快速的将修改后的字符串和bank里面的进行配对 答案是使用哈希表 这样子
class Solution
{
public:int minMutation(string startGene, string endGene, vectorstring bank) {unordered_setstring vis; // 用于标记已经访问过的基因防止重复搜索unordered_setstring hash(bank.begin(), bank.end()); // 将基因库中的基因存储到哈希集合中方便快速查找string change ACGT; // 基因可能包含的字符集用于生成所有可能的突变基因// 如果起始基因就是目标基因则不需要任何突变if(startGene endGene) return 0;// 如果目标基因不在基因库中则无法找到路径if(!hash.count(endGene)) return -1;queuestring q; // 使用队列进行广度优先搜索q.push(startGene); // 将起始基因加入队列vis.insert(startGene); // 标记起始基因为已访问int ret 0; // 记录突变次数// 当队列不为空时继续搜索while(q.size()){ret; // 每遍历一层突变次数加1int sz q.size(); // 当前层的基因数量// 遍历当前层的所有基因while(sz--){string t q.front(); // 取出当前基因q.pop(); // 从队列中移除当前基因// 对当前基因的每个位置进行突变尝试for(int i 0; i 8; i) // 假设基因长度为8这里需要根据实际情况调整{string tmp t; // 复制当前基因用于尝试突变// 对当前位置进行四种可能的突变for(int j 0; j 4; j){tmp[i] change[j]; // 尝试将当前位置的字符替换为A、C、G、T之一// 如果突变后的基因在基因库中且未被访问过if(hash.count(tmp) !vis.count(tmp)){// 如果找到了目标基因返回当前的突变次数if(tmp endGene) return ret;// 将突变后的基因加入队列继续搜索q.push(tmp);// 标记突变后的基因为已访问vis.insert(tmp);}}}}}// 如果遍历完所有可能的路径都没有找到目标基因则返回-1return -1;}
}; 题目三——127. 单词接龙 - 力扣LeetCode 这题简直和上面那题是一模一样的。
class Solution {
public:int ladderLength(string beginWord, string endWord, vectorstring wordList) {unordered_setstring vis;unordered_setstringhash(wordList.begin(),wordList.end());queuestringq;q.push(beginWord);vis.insert(beginWord);int ret1;//注意这里是从1开始的最开始的那个单词也算while(q.size()!0){ret;int szq.size();while(sz--){string tq.front();q.pop();for(int i0;ibeginWord.size();i){string tmpt;for(char na;nz;n){tmp[i]n;if(hash.count(tmp)!vis.count(tmp)){if(tmpendWord) return ret;q.push(tmp);vis.insert(tmp);}}}}}return 0;}
}; 题目四——675. 为高尔夫比赛砍树 - 力扣LeetCode 这个题目的意思必须得看懂啊
从低向高砍树 这个必须得注意啊
这样子这个题目就有意思了啊我们来解决一下
首先啊我们得知道我们需要先获取这个砍树的顺序啊我们可以遍历数组把值大于1的保存到一个数组里面然后对这个数组sort就获取到了这个砍树的顺序。
然后我们就按照这个顺序去砍树啊每次砍树时都调用BFS计算从当前点去砍树点的最短步数是多少每次寻找找一个砍树的点后就更新这个初始点然后将这个步数累计起来接下来重复之前的过程即可
class Solution {
public:int cutOffTree(vectorvectorint forest) {//获取砍树的顺序vectorpairint, int tree;for(int n0;nforest.size();n){for(int i0;iforest[0].size();i){if(forest[n][i]1){tree.push_back({n,i});}}}sort(tree.begin(), tree.end(), [](const pairint, int p1, const
pairint, int p2){return forest[p1.first][p1.second] forest[p2.first][p2.second];});// 2. 按照顺序砍树int bx 0, by 0;int ret 0;for(auto [a, b] : tree){int step bfs(forest, bx, by, a, b);if(step -1) return -1;ret step;bx a, by b;}return ret;}int dx[4]{0,0,-1,1};int dy[4]{-1,1,0,0};bool vis[51][51];int bfs(vectorvectorintforest,int i,int j,int bx,int by){if(bx i by j) return 0;queuepairint,intq;memset(vis, false, sizeof(vis)); // 清空之前的数据q.push({i,j});vis[i][j] true;int ret0;while(q.size()!0){ret;int szq.size();while(sz--){auto [a,b]q.front();q.pop();for(int k0;k4;k){int xadx[k],ybdy[k];if(x0xforest.size()y0yforest[0].size()forest[x][y]!0vis[x][y]false){if(x bx y by) return ret;q.push({x,y});vis[x][y]true;}}}}return -1;}
}; 4.多源BFS
其实BFS有多源BFS和单源BFS。
多源BFS与单源BFS有什么区别呢
单源BFS从某一个点开始起点多源BFS从多个点同时开始走
如何解决多源BFS
正常来说在我们会了单源BFS的使用后面对多个起点到一个终点的最短路问题也就是多源BFS我们最先想到的就是暴力做法也就是将多个起点分成一份份一个起点到一个终点的单源BFS问题这样我们每个起点到终点的最短路都求出来再找最小值即可但这种暴力几乎是一定超时的最差时间复杂度都达到ON^3
一个一个起点算最短路会超时那如果多个起点一块呢
这时我们就发现如果多个起点一块进行BFS搜索重复的路程不再经过这时不仅得出的答案正确而且时间复杂度大大降低这也就是多源BFS的核心思路多个起点同时用单源BFS的方法去找最短路
核心代码几乎跟单源BFS一样就是在最前面不是把一个起点加入队列而是把多个起点全部加入队列
事实上多源的BFS本质上与单源的BFS并无太大差别我们只需要把多个起点等效成一个起点即可这样就转化为了单源的问题了。
多源BFS多个起点 —— 多个起点同时加入队列 核心在求解多源BFS问题时同时将所有起点加入队列即可 注意BFS只能解决边权为1的多源最短路问题 题目一——542. 01 矩阵 - 力扣LeetCode 其实大家仔细看题目题目就是想要我们把这个数组修改成该点到最近的0的路径 对于求的最终结果我们有两种⽅式 第⼀种⽅式从每⼀个 1 开始然后通过层序遍历找到离它最近的 0 。 这⼀种⽅式我们会以所有的 1 起点来⼀次层序遍历势必会遍历到很多重复的点。并且如果 矩阵中只有⼀个 0 的话每⼀次层序遍历都要遍历很多层时间复杂度较⾼。换⼀种⽅式从 0 开始层序遍历并且记录遍历的层数。我们从0开始去寻找最近的1。当第⼀次碰到 1 的时候当前的层数 就是这个 1 离 0 的最短距离。 这⼀种⽅式我们在遍历的时候标记⼀下处理过的 1 能够做到只⽤遍历整个矩阵⼀次就能得 到最终结果。
但是这⾥有⼀个问题 0 是有很多个的我们怎么才能保证遇到的 1 距离这⼀个 0 是最近的 呢 其实很简单我们可以先把所有的 0 都放在队列中把它们当成⼀个整体每次把当前队列⾥⾯的所 有元素向外扩展⼀次。
class Solution {
public:// 更新矩阵函数输入是一个二维整数矩阵输出也是一个同样大小的二维整数矩阵// 输出矩阵中的每个元素表示从最近的零元素到该位置的最短距离vectorvectorint updateMatrix(vectorvectorint mat) {int n mat.size(); // 矩阵的行数int m mat[0].size(); // 矩阵的列数// 创建一个与输入矩阵大小相同的距离矩阵初始化为-1// -1 表示该位置尚未被搜索过// 非-1 值表示从最近的零元素到该位置的最短距离vectorvectorint distance(n, vectorint(m, -1));// 创建一个队列用于广度优先搜索queuepairint, int q;// 首先将所有为零的元素加入队列并将它们在距离矩阵中的值设为0// 因为这些零元素本身就是最近的零元素所以到它们自己的距离是0for (int i 0; i n; i) {for (int w 0; w m; w) {if (mat[i][w] 0) {q.push({i, w});distance[i][w] 0;}}}// 定义四个方向的行列偏移量用于在矩阵中移动int dx[4] {0, 0, -1, 1}; // 列偏移量左移、右移不变、上移、下移int dy[4] {-1, 1, 0, 0}; // 行偏移量上移、下移不变、左移、右移// 广度优先搜索while (!q.empty()) {int sz q.size(); // 当前队列中的元素数量即当前层的节点数// 遍历当前层的所有节点for (int i 0; i sz; i) {auto [a, b] q.front(); // 获取队列前端的节点坐标q.pop(); // 弹出已处理的节点// 遍历当前节点的四个相邻节点for (int k 0; k 4; k) {int x a dx[k]; // 计算相邻节点的行坐标int y b dy[k]; // 计算相邻节点的列坐标// 检查相邻节点是否在矩阵范围内且尚未被搜索过if (x 0 x n y 0 y m distance[x][y] -1) {// 更新相邻节点在距离矩阵中的值// 当前节点到相邻节点的距离是当前节点到零元素的距离加1distance[x][y] distance[a][b] 1;// 将相邻节点加入队列以便后续搜索q.push({x, y});}}}}// 返回更新后的距离矩阵return distance;}
}; distance[x][y] -1时我们必须知道这个mat[x][y]一定是1的。 因为这个mat[x][y]0的情况我们已经将distance[x][y]修改成0了 题目二——1020. 飞地的数量 - 力扣LeetCode 我们完全可以从边界开始往里面进行搜索将可以搜索到的1进行标记一下最后统计没有被标记的1即可。 修改数组元素版本 为了节约内存我直接把可以到达边界的1全都修改成了-1
class Solution {
public:// 计算完全被其他陆地包围的陆地的数量int numEnclaves(vectorvectorint grid) {int n grid.size(); // 获取网格的行数int m grid[0].size(); // 获取网格的列数queuepairint,int q; // 创建一个队列用于广度优先搜索BFS// 标记并加入边界上的陆地到队列中for (int i 0; i n; i) {// 处理第一列if (grid[i][0] 1) {grid[i][0] -1; // 标记为已访问q.push({i, 0}); // 加入队列进行BFS}// 处理最后一列if (grid[i][m-1] 1) {grid[i][m-1] -1; // 标记为已访问q.push({i, m-1}); // 加入队列进行BFS}}// 处理第一行和最后一行for (int i 0; i m; i) {// 处理第一行if (grid[0][i] 1) {grid[0][i] -1; // 标记为已访问q.push({0, i}); // 加入队列进行BFS}// 处理最后一行if (grid[n-1][i] 1) {grid[n-1][i] -1; // 标记为已访问q.push({n-1, i}); // 加入队列进行BFS}}// 定义四个方向的行列偏移量用于在矩阵中移动int dx[4] {0, 0, -1, 1}; // 列偏移量左移、右移不变、上移、下移int dy[4] {-1, 1, 0, 0}; // 行偏移量上移、下移不变、左移、右移// 从边界上的陆地开始进行广度优先搜索BFSwhile (!q.empty()) {int sz q.size(); // 当前层级的节点数量while (sz--) {auto [a, b] q.front(); // 获取当前节点的坐标q.pop(); // 从队列中移除当前节点// 遍历四个方向for (int k 0; k 4; k) {int x a dx[k], y b dy[k]; // 计算新坐标// 检查新坐标是否在网格内且为陆地值为1if (x 0 x n y 0 y m grid[x][y] 1) {grid[x][y] -1; // 标记为已访问q.push({x, y}); // 加入队列进行下一轮BFS}}}}// 统计剩余的陆地飞地数量int ret 0;for (int i 0; i n; i) {for (int w 0; w m; w) {if (grid[i][w] 1) {ret; // 统计飞地数量}}}return ret; // 返回飞地数量}
}; 使用bool数组版本 class Solution
{// 定义四个方向的行列偏移量用于在矩阵中移动int dx[4] {0, 0, 1, -1}; // 列偏移量左移、右移不变、上移、下移int dy[4] {1, -1, 0, 0}; // 行偏移量上移、下移不变、左移、右移public:// 计算完全被其他陆地包围的陆地的数量int numEnclaves(vectorvectorint grid) {int m grid.size(); // 获取网格的行数int n grid[0].size(); // 获取网格的列数// 创建一个二维布尔数组用于标记每个位置是否已被访问过vectorvectorbool vis(m, vectorbool(n, false));// 创建一个队列用于广度优先搜索BFSqueuepairint, int q;// 1. 将边上的陆地加入到队列中并标记为已访问for (int i 0; i m; i){for (int j 0; j n; j){// 检查当前位置是否在网格的边上if (i 0 || i m - 1 || j 0 || j n - 1){// 如果边上的位置是陆地值为1if (grid[i][j] 1){// 将该位置加入队列进行BFSq.push({i, j});// 标记该位置为已访问vis[i][j] true;}}}}// 2. 进行多源BFS从队列中取出陆地并标记其相邻的陆地while (!q.empty()){auto [a, b] q.front(); // 获取当前陆地的坐标q.pop(); // 从队列中移除当前陆地// 遍历四个方向for (int i 0; i 4; i){int x a dx[i], y b dy[i]; // 计算相邻陆地的坐标// 检查相邻陆地是否在网格内、是陆地且未被访问过if (x 0 x m y 0 y n grid[x][y] 1 !vis[x][y]){// 标记相邻陆地为已访问vis[x][y] true;// 将相邻陆地加入队列进行下一轮BFSq.push({x, y});}}}// 3. 统计结果遍历整个网格计算未被访问的陆地的数量int ret 0;for (int i 0; i m; i){for (int j 0; j n; j){// 如果当前位置是陆地且未被访问过则它是一个飞地if (grid[i][j] 1 !vis[i][j]){ret; // 增加飞地的计数}}}return ret; // 返回飞地的数量}
}; 题目三—— 1765. 地图中的最高点 - 力扣LeetCode 我们应该从水域向外扩展。???这不就跟那个矩阵那题是一模一样的思路吗
class Solution {// 定义四个方向的行列偏移量用于在矩阵中移动int dx[4] {0, 0, 1, -1}; // 列偏移量左移、右移不变、上移、下移int dy[4] {1, -1, 0, 0}; // 行偏移量上移、下移不变、左移、右移
public:vectorvectorint highestPeak(vectorvectorint isWater) {int nisWater.size(),misWater[0].size();vectorvectorintret(n,vectorint(m,-1));queuepairint,intq;for(int i0;in;i){for(int w0;wm;w){if(isWater[i][w]1){q.push({i,w});ret[i][w]0;}}}int step0;while(q.size()!0){step;int szq.size();while(sz--){auto [a,b]q.front();q.pop();for(int k0;k4;k){int xadx[k],ybdy[k];if(x0xny0ymret[x][y]-1){ret[x][y]ret[a][b]1;q.push({x,y});}}}}return ret;}
}; 题目四—— 1162. 地图分析 - 力扣LeetCode 嗯仔细看一下题目这不是01矩阵吗
class Solution {// 定义四个方向的行列偏移量用于在矩阵中移动int dx[4] {0, 0, 1, -1}; // 列偏移量左移、右移不变、上移、下移int dy[4] {1, -1, 0, 0}; // 行偏移量上移、下移不变、左移、右移
public:int maxDistance(vectorvectorint grid) {int ngrid.size(),mgrid[0].size();vectorvectorint end(n,vectorint(m,-1));queuepairint,intq;for(int i0;in;i){for(int w0;wm;w){if(grid[i][w]1){q.push({i,w});end[i][w]0;}}}int path0;int ret-1;while(q.size()!0){path;int szq.size();while(sz--){auto [a,b]q.front();q.pop();for(int k0;k4;k){int xadx[k],ybdy[k];if(x0xny0ymend[x][y]-1){end[x][y]end[a][b]1;q.push({x,y});retmax(ret,path);}}}}return ret;}
}; 5.BFS解决拓扑排序
要知道什么拓扑排序我们首先要知道什么是有向无环图有向无环图我们看名字其实就很容易理解有向就是有方向无环就是没有环形结构。
在图论中如果一个有向图无法从某个顶点出发经过若干条边回到该点则这个图是一个有向无环图DAG图。
有向无环图指的是有方向但没有环的图。
图就是一个顶点和边连接而成的一个数据结构有向图就是边都是有方向的。有向无环图就是图中是没有环的。如不能从1-2-33-2-4 所以这个图就是一个有向无环图。 如 4-5-6 是可以走通的这就不是有向无环图了。 接下来我们来介绍一下有向图中的一些专业术语
入度Indegree一个顶点的入度是指有多少条边指向这个顶点。换句话说它表示该顶点有多少个直接前驱节点。简单来说就是对于一个顶点来说所有指向他的边之和出度Outdegree一个顶点的出度是指从这个顶点出发有多少条边。也就是说它表示该顶点有多少个直接后继节点。简单来说对于一个顶点来说这个顶点往外伸出的边的总和 接下来我们来说说AOV网也就是顶点活动图。 AOV网也叫做顶点活动图它其实是一个有向无环的一个应用。
在有向无环图中用顶点来表示一个活动用边来表示执行活动的先后顺序的图结构
比如我想洗菜我得先买菜我想腌肉需要先买菜和准备厨具。。 3.拓扑排序 概念略
大白话意思就是在AOV网中找到做事情的先后顺序。
可以看到在这些活动中其中一些活动必须在某些活动执行之后才能执行比如说炒菜必须先切菜腌肉。所以在整个工程中这个炒菜绝对不可能先干。 那些活动可以先干呢可以看到准备厨具、买菜可以先干原因就是并没有边执行它们俩。可以先准备厨具或者先买菜。所以从这里就可以发现一点拓扑排序的结果可能不是唯一的
如果先买菜买完菜之后与买菜相连的箭头就可以删掉了因为买完菜就可以解锁洗菜的操作了。所以这个箭头就可以删去了。。 接下来可以准备厨具或者洗菜原因是它俩都没有其他条件来限制。可以任选一个。 接下来只能洗菜。。。。。同理重复上面操作最后我们就可以得到这样的做事情先后的序列这也是就是拓扑排序的序列。找到做事情的先后顺序。 如何排序
找出图中入度为 0 的点然后输出删除与该点相连的边重复1、2操作直到图中没有点或者没有入度为 0 的点为止
图中没有点理解所有活动都找完了可以停止了此时的序列就是拓扑排序的序列。
图中没有入度为 0 的点是怎么回事
其实就是在这个拓扑排序中可能面对的不是有向无环图是有环形结构的。
比如下面这个图刚开始并不知道这个有向图是不是有环的所以我们可以先做一下拓扑排序
当把1、3、2拿出来之后发现剩下的都拿不出来了。原因就是4、5、6形成一个环路是没有入度为0的边。 因此这个结束条件还需要加上直到图中没有入度为 0 的点为止 原因就是可能有环
所以说拓扑排序有一个特别重要的应用判断有向图中是否有环。 如何判断有向图中是否有环 直接对图来一次拓扑排序当拓扑排序过程中发现没有入度为0的点的时候但是图中还有剩余点的时候此时这个图中一定会有环形结构。 4.实现拓扑排序 借助队列来一次 BFS 即可
初始化把所有入度为 0 的点加入到队列中
当队列不为空的时候
拿出队头元素加入到最终结果中删除与该元素相连的边判断与删除边相连的点是否入度变成 0 如果入度为 0加入到队列中
这里还有一个问题没说如何建图 如何表示一个点的入度呢下面的题在说。建完图然后搞拓扑排序。 题目一——207. 课程表 - 力扣LeetCode 其实这道题问题的就是有向图中是否有环。
我们可以把给的信息抽象称一张有向图题目问能否完成所有课程学习意思就是能不能把这个课程排个序说白了就是能否拓扑排序能否拓扑排序也就是是否这个图是否是有向无环图 — 有向图中是否有环 做一次拓扑排序即可前面已经说过如何拓扑排序接下来重点就是如何建图
如何建图灵活使用语言提供的容器
看稠密看数据量
邻接矩阵稠密图邻接表稀疏图
这道题我们用邻接表建图
相像中的邻接表最左边代表某个节点这个节点右边一坨代表这个点所连接的点。
看起来就像一个个链表头表示当前所考虑的这个节点后面相连所有的节点是与我当前点相连的节点。我们建图的目的就是为了方便找到某个点所连接的那个点。不然还要遍历数组去找太麻烦了所以把这些东西先存到一个数据结构中这个数据结构就是图。
邻接表我们脑海中想到的应该就是这样的一条一条链表的结构。 那如何实现一个邻接表呢
我们没有必须真的搞一个链表出来这里有两种方式
vectorvector edgesunordered_mapint,vector edges
用vector嵌套一个vector是比较局限的只能用于节点里面的值是数字表示的。
用unordered_map是比较万能的可以把int — string vector int — vector string 等等其他任何类型。
vector嵌套一个vector通过下标可以找到与这个节点的值相连的其他节点。仅需在对应下标的vector做push_back就可以把与当前节点相连的节点加入。 用unordered_map就比较万能了完全像刚才想象出来的邻接表结构我们这里是一个int的数后面挂了一个int数组那不就和一个节点挂着一个节点的效果一样的吗。用数组表示所连接的节点。 根据算法流程灵活建图
刚才我们只是实现把所有的边存起来。我们还要根据算法流程多添加一些东西。
比如这里我们是做拓扑排序因此我们需要直到每个顶点的入度是多少。可以搞一个vector int in数组里面的值就表示这个顶点的入度是多少。 总结建图先看数据量选择邻接矩阵还是邻接表来建图然后根据算法流程灵活的在建图的基础上多添加上一点东西。 class Solution {
public:bool canFinish(int n, vectorvectorint prerequisites) {// 1. 准备工作unordered_mapint,vectorint edges;//邻接表存图vectorint in(n);// 标记每一个顶点的入度// 2. 建图for(auto e : prerequisites){int a e[0], b e[1];// b - a 的一条边edges[b].push_back(a);// 把与b相连的顶点添加对应数组in[a];// 记录对应顶点的入度}// 3. 拓扑排序queueint q;// (1) 把所有入度为 0 的顶点加入到队列中for(int i 0; i n; i){if(in[i] 0)q.push(i);}// (2) bfswhile(q.size()){int t q.front();q.pop();//这道题没有让求顺序//把与这个顶点相连的边干掉,就是修改与其相连顶点的入度for(auto a : edges[t]){in[a]--;//入度-1if(in[a] 0)//入度变为0加入队列q.push(a);}}// 4.判断是否有环//如果整个拓扑排序结束之后,每个顶点的入度都变成0了说明没有环,否则就有环for(int i 0; i n; i){if(in[i]) return false;}return true;}
};题目二——210. 课程表 II - 力扣LeetCode 这道题和上面是一模一样的还是做一次拓扑排序不同的是这次要把拓扑排序顺序返回来。
class Solution {
public:vectorint findOrder(int numCourses, vectorvectorint prerequisites) {vectorintin(numCourses,0);unordered_mapint,vectorintend;for(autotmp:prerequisites){int atmp[0],btmp[1];end[b].push_back(a);in[a];}queueintq;vectorintret;for(int i0;inumCourses;i){if(in[i]0){q.push(i);}}while(q.size()){int aq.front();q.pop();ret.push_back(a);for(autotmp:end[a]){in[tmp]--;if(in[tmp]0){q.push(tmp);}}}if(ret.size()numCourses) return ret;else return {};}
};
