c2c的代表性的电商平台_如何建立自己的网站教程_磁力多多_建站公司网站建设

---

前言

一、单源最短路问题

边权相等的最短路。
从起点开始，进行一次BFS操作。需要借助队列和数组（是否遍历过）完成操作。
弹出前，先计算队列中有多少元素，同时向外扩展。
最短路径就是层序遍历的层数

433. 最小基因变化

题目解析

433. 最小基因变化添加链接描述

做完上面这道题目可以做一下这道题目。代码放到最后了。

127. 单词接龙

算法原理

本道题木是经典的单源最短路问题，虽然题目没有直接说明，但是经过我们的分析是可以分析出来的。

1.用哈希表来解决转换后是否存在bank中
2.用哈希表判断是否已经转换过了
3.我们每个字符串都有8个位置可以转换，并且每次都有四种选择
4.向外扩展的次数就是我们的结果，要注意队列里面的元素要同时向外扩展。

代码编写

class Solution {
public:int minMutation(string startGene, string endGene, vector<string>& bank) {//哈希表存放，方便快速查找unordered_set<string> hash(bank.begin(),bank.end());//特殊情况if(startGene==endGene) return 0;if(hash.count(endGene)==0) return -1;//标记是否遍历过unordered_set<string>vis;queue<string>q;q.push(startGene);vis.insert(startGene);//记录次数int ret=0;while(!q.empty()){ret++;int sz=q.size();//同时扩展while(sz--){string s=q.front();q.pop();string change="ACGT";//8个位置for(int i=0;i<8;i++){//每次只能变化一个位置string tmp=s;//4种变化for(int j=0;j<4;j++){tmp[i]=change[j];if(tmp==endGene) return ret;if(hash.count(tmp)&&!vis.count(tmp)){q.push(tmp);vis.insert(tmp);}}}}}return -1;}
};

127. 单词接龙

class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {unordered_set<string>hash(wordList.begin(),wordList.end());unordered_set<string>vis;//特殊处理if(hash.count(endWord)==0) return 0;int len=beginWord.size();queue<string>q;q.push(beginWord);vis.insert(beginWord);//记录次数,注意根据题目要求要从1开始int ret=1;while(!q.empty()){ret++;int sz=q.size();//同时扩展while(sz--){string s=q.front();q.pop();//一共len个字符for(int i=0;i<len;i++){string tmp=s;//26个英文字母for(int j=0;j<26;j++){tmp[i]='a'+j;if(tmp==endWord) return ret;if(hash.count(tmp)&&!vis.count(tmp)){q.push(tmp);vis.insert(tmp);}}}}}return 0;}
};

675. 为高尔夫比赛砍树

题目解析

675. 为高尔夫比赛砍树

算法原理

1.我们通过对数组下标进行排序，确定砍树的先后顺序
2.两个树之间进行一个BFS，确定出最短路径，依次遍历即可

代码编写

class Solution {
public:int m,n;int dx[4]={0,0,-1,1};int dy[4]={1,-1,0,0};int cutOffTree(vector<vector<int>>& f) {m=f.size();n=f[0].size();//对数组下标进行排序vector<pair<int,int>>tree;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(f[i][j]>1) tree.push_back({i,j});}}sort(tree.begin(),tree.end(),[&](pair<int,int>p1,pair<int,int>p2){return f[p1.first][p1.second]<f[p2.first][p2.second];});int fx=0;int fy=0;int sum=0;//砍树for(auto [fa,fb]:tree){int step=bfs(f,fx,fy,fa,fb);if(step==-1) return -1;sum+=step;fx=fa;fy=fb;}return sum;}int bfs(vector<vector<int>>& f,int fx,int fy,int fa,int fb){//起始位置和终止位置相同if(fx==fa&&fy==fb) return 0;queue<pair<int,int>>q;int vis[m][n];memset(vis,false,sizeof(vis));q.push({fx,fy});vis[fx][fy]=true;int step=0;while(!q.empty()){step++;int sz=q.size();while(sz--){auto [a,b]=q.front();q.pop();for(int i=0;i<4;i++){int x=a+dx[i];int y=b+dy[i];if(x>=0&&x<m&&y>=0&&y<n&&f[x][y]>=1&&!vis[x][y]){if(x==fa&&y==fb) return step;else {q.push({x,y});vis[x][y]=true;}}}}}return -1;} 
};

二、多源最短路问题

多元BFS：用bfs解决边权为一的多源做短路问题。
如何解决：
1.暴力方法，把多源最短路问题转化成若干个单源最短路问题，但是这样会超时，时间复杂度太高。

2.把所有源点当成一个超级源点，问题就变成了单源最短路问题

代码编写：把所有起点加入到队列中，一层层扩展

542. 01 矩阵

题目解析

542. 01 矩阵

算法原理

我们本道题就是经典的多源最短路问题，我们按照题目要求把1当作起点，放入队列中，但是这样解题会很麻烦。

正难则反
我们可以把0加入到队列中，进行扩展

我们不需要用上面的step，vis数组等，
我们直接用一个dist数组表示距离就可以：
如果为-1表示没有遍历过；如果不为-1，就表示最短路径

代码编写

class Solution {
public:int dx[4]={0,0,-1,1};int dy[4]={1,-1,0,0};vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {//从所有0位置开始扩展int m=mat.size();int n=mat[0].size();vector<vector<int>>dist(m,vector<int>(n,-1));queue<pair<int,int>>q;for(int i=0;i<m;i++)for(int j=0;j<n;j++)if(mat[i][j]==0) {q.push({i,j});dist[i][j]=0;}//注意这里为社么可以while(!q.empty()){auto [a,b]=q.front();q.pop();for(int i=0;i<4;i++){int y=b+dy[i]; int x=a+dx[i];if(x>=0&&x<m&&y>=0&&y<n&&dist[x][y]==-1){dist[x][y]=dist[a][b]+1;q.push({x,y});  }}}return dist;}
};

1020. 飞地的数量

题目解析

1020. 飞地的数量

算法原理

我们结合上道题目，本道题的难点就是如何找到个数，这个直接求是很困难的

正难则反
因为边界上的块不能统计进最后的结果中，那我们就对边上的点进行·BFS遍历，最后遍历一遍数组，我们没有遍历过的并且值为1，就是我们需要返回的结果。

代码编写

我们这里遍历四条边有两种写法。
第二种很好写，不容易出错，但是时间复杂度高

class Solution {
public:int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};int numEnclaves(vector<vector<int>>& grid) {queue<pair<int,int>>q;int m=grid.size();int n=grid[0].size();vector<vector<bool>>vis(m,vector<bool>(n,false));// for(int i=0;i<m;i++)// {//     if(grid[i][0]==1)//     {//         q.push({i,0});//         vis[i][0]=true;//     }//     if(grid[i][n-1]==1)//     {//         q.push({i,n-1});//         vis[i][n-1]=true;//     }// }// for(int j=0;j<n;j++)// {//     if(grid[0][j]==1)//     {//         q.push({0,j});//         vis[0][j]=true;//     }//     if(grid[m-1][j]==1)//     {//         q.push({m-1,j});//         vis[m-1][j]=true;//     }// }//遍历四条边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){if(grid[i][j]==1){q.push({i,j});vis[i][j]=true;}}}}while(!q.empty()){auto [a,b]=q.front();q.pop();for(int i=0;i<4;i++){int x=a+dx[i];int y=b+dy[i];if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]==1&&vis[x][y]==false){q.push({x,y});vis[x][y]=true;}}}//计算int total=0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1&&vis[i][j]==false){total++;}}}return total;}
};

总结

以上就是今天要讲的内容 。希望对大家的学习有所帮助，仅供参考 如有错误请大佬指点我会尽快去改正 欢迎大家来评论~~ 😘 😘 😘