服务定制网站,做外贸站推广,常州app开发公司,昌大建设集团1. 多源最短路
其实就是将所有源头都加入队列#xff0c;
01矩阵
LCR 107. 01 矩阵 - 力扣#xff08;LeetCode#xff09; 思路
求每个元素到离其最近0的距离如果我们将1当做源头加入队列的话#xff0c;无法处理多个连续1的距离存储#xff0c;我们反其道而行之
01矩阵
LCR 107. 01 矩阵 - 力扣LeetCode 思路
求每个元素到离其最近0的距离如果我们将1当做源头加入队列的话无法处理多个连续1的距离存储我们反其道而行之将所有的终点存进队列遍历离其最近的1当然如果旁边是0无需入队(因为旁边这个0找到的1肯定比他快一步)是1才要入队先遍历到1的步数一定是最小的步数。
ac代码
class Solution {
public:vectorvectorint updateMatrix(vectorvectorint mat) {int mmat.size();//int nmat[0].size();vectorvectorint states(m,vectorint(n,-1));int dx[4]{1,0,0,-1};int dy[4]{0,1,-1,0};for(int i0;im;i){for(int j0;jn;j){if(mat[i][j]0)//从终点开始找{qu.push({i,j});states[i][j]0;}}}while(!qu.empty()){int x1qu.front().first;int y1qu.front().second;qu.pop();for(int i0;i4;i){int x2x1dx[i];int y2y1dy[i];if(x20||x2m||y20||y2n)continue;if(mat[x2][y2]0||states[x2][y2]!-1)//同为0或者走过了先走的肯定更小continue;states[x2][y2]states[x1][y1]1;qu.push({x2,y2});}}return states;}private:queuepairint,int qu;}; 飞地的数量
1020. 飞地的数量 - 力扣LeetCode 思路
解法1
(非多源bfs)遍历地图将遇到的并且没有走过的1进行bfs如果没有陆地在边缘返回值为连通的陆地数量在边缘就返回0将返回值累加起来即可。
解法2 (多源bfs)先考虑什么可以当源头所有的1明显不可以0进去也得不出来结果。我们发现题目的关键点在于边缘的陆地就不是飞地所以我们将所有在边缘的陆地入队然后查找与这些陆地相连的其他陆地将其标记最后遍历地图查找没被标记的陆地即可。
ac代码
class Solution {
public:int bfs(vectorvectorint grid,int x,int y){int mgrid.size();int ngrid[0].size();int dx[4]{1,0,0,-1};int dy[4]{0,1,-1,0};queuepairint,int qu;qu.push({x,y});states[x][y]true;int cnt1;//记录有多少个陆地bool ftrue;//如果有边缘就变falsewhile(!qu.empty()){int x1qu.front().first;int y1qu.front().second;qu.pop();for(int i0;i4;i){int x2x1dx[i];int y2y1dy[i];if(x20||x2m||y20||y2n){ffalse;//有靠边缘的continue;}if(states[x2][y2]!false||grid[x2][y2]0)continue;states[x2][y2]true;//走过qu.push({x2,y2});cnt;}}if(f)return cnt;elsereturn 0;}int numEnclaves(vectorvectorint grid) {int mgrid.size();int ngrid[0].size();memset(states,false,sizeof states);int sum0;for(int i0;im;i){for(int j0;jn;j){if(grid[i][j]1!states[i][j]){sumbfs(grid,i,j);}}}return sum;}private:bool states[510][510];
};
地图分析
1162. 地图分析 - 力扣LeetCode 思路
统计海洋单位与离其最近的陆地的距离直接将所有陆地视为源头四散记录自己离海洋的距离即可。每到一个海洋就比较到这个海洋的距离与之前记录的到海洋的距离那个更远。
ac代码
class Solution {
public:int maxDistance(vectorvectorint grid) {int ngrid.size();int dx[4]{1,0,0,-1};int dy[4]{0,-1,1,0};vectorvectorint states(n,vectorint(n,-1));for(int i0;in;i){for(int j0;jn;j){if(grid[i][j]1){qu.push({i,j});states[i][j]0;}}}while(!qu.empty()){int x1qu.front().first;int y1qu.front().second;qu.pop();for(int i0;i4;i){int x2x1dx[i];int y2y1dy[i];if(x20||x2n||y20||y2n)continue;if(grid[x2][y2]1||states[x2][y2]!-1)//不是陆地不能走过continue;states[x2][y2]states[x1][y1]1;cntmaxmax(cntmax,states[x2][y2]);qu.push({x2,y2});}}return cntmax;}private:int cntmax-1;queuepairint,int qu;//存陆地};
地图中的最高点
1765. 地图中的最高点 - 力扣LeetCode 思路
题目很直观将所有的水域入队然后四处扩散增加即可。
ac代码
class Solution {
public:vectorvectorint highestPeak(vectorvectorint isWater) {int misWater.size();//int nisWater[0].size();vectorvectorint states(m,vectorint(n,-1));int dx[4]{1,0,0,-1};int dy[4]{0,1,-1,0};for(int i0;im;i){for(int j0;jn;j){if(isWater[i][j]1)//从水开始{qu.push({i,j});states[i][j]0;//水域为0}}}while(!qu.empty()){int x1qu.front().first;int y1qu.front().second;qu.pop();for(int i0;i4;i){int x2x1dx[i];int y2y1dy[i];if(x20||x2m||y20||y2n)continue;if(isWater[x2][y2]1||states[x2][y2]!-1)//都为水域或者走过了先走的肯定更小continue;states[x2][y2]states[x1][y1]1;qu.push({x2,y2});}}return states;}private:queuepairint,int qu;
};
2. 拓扑排序问题
将问题变成一个有向无环图解决拓扑排序要找到做事情的先后顺序结果可能不是唯一的。
如下图 有几个通向自己的节点入度就为几
我们找到图中入度为0的点a必须将a消除后使b和c的入度也从1变为0才可以消除b和c必须把b和c都消除后才能将d的入度变为0再消除b。
实现拓扑排序的具体步骤 借助队列queue 1. 初始化把所有入度为0的点加入到队列中 2. 当队列不为空时 (1)拿出队头元素加到最终结果上 (2)删除与该元素相连的边 (3)判断删除边相连的点是否入度变为了0为0就入队 可以创建邻接矩阵来构造图
也可以创建邻接表来构造vectorvectorint 或者 unordered_mapint,vectorint
课程表
207. 课程表 - 力扣LeetCode 思路
创建一个哈希表来记录每个课程之间的关系将完成x课程的前置课程y1y2等都存储起来创建一个数组记录每个课程的入度
ac代码
class Solution {
public:bool canFinish(int numCourses, vectorvectorint prerequisites) {in.resize(numCourses,0);int mprerequisites.size();for(int i0;im;i){//数组里只有两个数map[prerequisites[i][1]].push_back(prerequisites[i][0]);//b[i]通向a[i]in[prerequisites[i][0]];//a[i]多一个前置条件}for(int i0;iin.size();i){if(in[i]0)//没前置条件qu.push(i);//将这门课程入队}int cnt0;while(!qu.empty()){int tmpqu.front();qu.pop();cnt;//for(int i0;imap[tmp].size();i)//删除这个前置其链接的点少一个前置{in[map[tmp][i]]--;if(in[map[tmp][i]]0)//前置都完成了{qu.push(map[tmp][i]);}}}if(cntnumCourses)return true;elsereturn false;}private:unordered_mapint,vectorint map;//邻接表vectorint in;//记录每个课程的入度queueint qu;
};
课程表 II
LCR 113. 课程表 II - 力扣LeetCode 思路
与上题没什么不同就是多一个数组来记录可以学习的课程
ac代码
class Solution {
public:vectorint findOrder(int numCourses, vectorvectorint prerequisites) {in.resize(numCourses,0);int mprerequisites.size();for(int i0;im;i){map[prerequisites[i][1]].push_back(prerequisites[i][0]);//将b[i]后置保存起来in[prerequisites[i][0]];//这个课程前置加1}for(int i0;iin.size();i){if(in[i]0)qu.push(i);}vectorint nums;while(!qu.empty()){int tmpqu.front();qu.pop();nums.push_back(tmp);for(int i0;imap[tmp].size();i){in[map[tmp][i]]--;if(in[map[tmp][i]]0)qu.push(map[tmp][i]);}}if(nums.size()numCourses)return nums;elsenums.resize(0,0);return nums;}unordered_mapint,vectorint map;//邻接表vectorint in;//记录自身有多少前置queueint qu;
};
火星词典
LCR 114. 火星词典 - 力扣LeetCode 思路
如何建图 将第一个字符串与之后所有字符串对比(双指针一个字符一个字符对比)然后再将第二个字符串与第二个字符串之后所有字符串对比依次类推...有不一样的就检测哈希表中x字符有没有已经存入相同的前置字符没有再存进去然后break再往后也找不出来了要注意当数组走完并且第二个数组比第一个数组小时是错误的要特判一下
记录入度
用一个哈希表进行记录
for(auto [a,b]:in)//in中char会存到a里入度的值会存到b里
//用来遍历in数组解决问题与上方差不多
ac代码
class Solution {
public:string alienOrder(vectorstring words) {//所有前置走完走接下来的int m words.size();for (auto tmp : words)//初始化入度{for (auto t : tmp){in[t] 0;}}for (int i 0; i m - 1; i){for (int j i 1; j m; j){int nmin(words[i].size(),words[j].size());string s1words[i];string s2words[j];int t0;for( t0;tn;t){if(s1[t]!s2[t])//不相等再存{if(!map[s1[t]].count(s2[t]))//看s1[t]其中有没有存s2[t]{map[s1[t]].insert(s2[t]);in[s2[t]];}break;//发现不同就不用往后找了}}if(ts2.size()ts1.size())return ;}}int cnt0;for(auto [a,b]:in)//in中char会存到a里入度的值会存到b里{if(b0) qu.push(a);cnt;}string s ;while (!qu.empty()){char tmp qu.front();qu.pop();s tmp;for (auto ch : map[tmp])//遍历哈希表{in[ch]--;if (in[ch] 0)qu.push(ch);}}if(s.size()cnt)return s;elsereturn ;}unordered_mapchar, unordered_setchar map;//unordered_mapchar, int in;//记录这个单词还有多少单词queuechar qu;
}; 这篇就到这里了(๑′ᴗ‵๑) Lᵒᵛᵉᵧₒᵤ❤
