佛山高端网站建设报价,六安哪家做网站不错,品牌营销是什么工作,济南网站建设有限公司目录
无权图的单源最短路问题#xff1a;
1. 迷宫中离入口最近的出口#xff08;中等#xff09;
2. 最小基因变化#xff08;中等#xff09;
3. 单词接龙#xff08;困难#xff09;
4. 为高尔夫比赛砍树#xff08;困难#xff09;
无权图的多源最短路问题
1. 迷宫中离入口最近的出口中等
2. 最小基因变化中等
3. 单词接龙困难
4. 为高尔夫比赛砍树困难
无权图的多源最短路问题
1. 01矩阵中等
2. 地图中的最高点中等
3. 地图分析中等 无权图的单源最短路问题
使用单源BFS可以求解无权图的单源最短路问题这是由BFS总是按照距离由近到远来遍历图中每个顶点的性质决定的。
1. 迷宫中离入口最近的出口中等
class Solution {
public:int nearestExit(vectorvectorchar maze, vectorint entrance) {int m maze.size();int n maze[0].size();vectorvectorbool visited(m, vectorbool(n));int ans 0;// 坐标上下左右的偏移量int dr[4] { -1,1,0,0 };int dc[4] { 0,0,-1,1 };queuepairint, int q;// 起始坐标入队并标记q.push({entrance[0], entrance[1]});visited[entrance[0]][entrance[1]] true;while (!q.empty()){// 要向外拓展一层步数ans;int count q.size(); // 本层坐标点的个数for (int i 0; i count; i){// 队头出队auto [row, col] q.front();q.pop();// 判断刚才出队的坐标上下左右是否满足条件再判断是否到达出口到达则直接返回没到达则入队并标记for (int j 0; j 4; j){int r row dr[j];int c col dc[j];if (r 0 r m c 0 c n maze[r][c] . !visited[r][c]){if (r 0 || r m - 1 || c 0 || c n - 1) // 到达出口return ans;q.push({r, c});visited[r][c] true;}}}}return -1;}
};
2. 最小基因变化中等
将距离为1变化了一个字符的字符串连接起来构成一个无权图求start到end的最短路。
class Solution {
public:int minMutation(string startGene, string endGene, vectorstring bank) {unordered_setstring hash(bank.begin(), bank.end()); // 哈希表记录基因库中的字符串unordered_setstring visited; // 标记字符串是否被访问过string change ACGT;if (startGene endGene)return 0;if (!hash.count(endGene))return -1;int ans 0;queuestring q;// 起始字符串入队并标记q.push(startGene);visited.insert(startGene);while (!q.empty()){// 要向外拓展一层步数ans;int count q.size(); // 本层字符串的个数for (int i 0; i count; i){// 队头出队string cur q.front();q.pop();// 判断刚才出队的字符串只改变一个字符后是否满足条件再判断是否到达end到达则直接返回没到达则入队并标记for (int i 0; i 8; i){string tmp cur;for (int j 0; j 4; j){tmp[i] change[j];if (hash.count(tmp) !visited.count(tmp)){if (tmp endGene) // 到达endreturn ans;q.push(tmp);visited.insert(tmp);}}}}}return -1;}
};
3. 单词接龙困难
和上一题“最小基因变化”类似区别是上一题求步数本题求最短路的顶点数。
class Solution {
public:int ladderLength(string beginWord, string endWord, vectorstring wordList) {unordered_setstring hash(wordList.begin(), wordList.end()); // 哈希表记录字典中的单词unordered_setstring visited; // 标记单词是否被访问过if (!hash.count(endWord))return 0;int ans 1;queuestring q;// 起始单词入队并标记q.push(beginWord);visited.insert(beginWord);while (!q.empty()){// 要向外拓展一层顶点数ans;int count q.size(); // 本层单词的个数for (int i 0; i count; i){// 队头出队string cur q.front();q.pop();// 判断刚才出队的单词只改变一个字符后是否满足条件再判断是否到达end到达则直接返回没到达则入队并标记for (int i 0; i cur.size(); i){string tmp cur;for (char ch a; ch z; ch){tmp[i] ch;if (hash.count(tmp) !visited.count(tmp)){if (tmp endWord) // 到达endreturn ans;q.push(tmp);visited.insert(tmp);}}}}}return 0;}
};
4. 为高尔夫比赛砍树困难 1 - 2 - 3 - 4 - 5 - 6 - 7
给树按从小到大排序求顺序相邻的树的最短路。
class Solution {
public:int cutOffTree(vectorvectorint forest) {m forest.size();n forest[0].size();// 给树按从小到大排序确定砍树的顺序vectorpairint, int trees;for (int i 0; i m; i){for (int j 0; j n; j){if (forest[i][j] 1){trees.push_back({i, j});}}}sort(trees.begin(), trees.end(), [](const pairint, int p1, const pairint, int p2){return forest[p1.first][p1.second] forest[p2.first][p2.second];});// 求顺序相邻的树的最短路int beginr 0;int beginc 0;int ans 0;for (auto [endr, endc] : trees){int step bfs(forest, beginr, beginc, endr, endc);if (step -1)return -1;ans step;beginr endr;beginc endc;}return ans;}private:int bfs(vectorvectorint forest, int beginr, int beginc, int endr, int endc){if (beginr endr beginc endc)return 0;vectorvectorbool visited(m, vectorbool(n)); // 标记坐标是否被访问过int ans 0;queuepairint, int q;// 起始坐标入队并标记q.push({beginr, beginc});visited[beginr][beginc] true;while (!q.empty()){// 要向外拓展一层步数ans;int count q.size(); // 本层坐标点的个数for (int i 0; i count; i){// 队头出队auto [row, col] q.front();q.pop();// 判断刚才出队的坐标上下左右是否满足条件再判断是否到达end到达则直接返回没到达则入队并标记for (int j 0; j 4; j){int r row dr[j];int c col dc[j];if (r 0 r m c 0 c n forest[r][c] !visited[r][c]){if (r endr c endc) // 到达endreturn ans;q.push({r, c});visited[r][c] true;}}}}return -1;}// 坐标上下左右的偏移量int dr[4] { -1,1,0,0 };int dc[4] { 0,0,-1,1 };int m;int n;
};
无权图的多源最短路问题
使用多源BFS可以求解无权图的多源最短路问题将所有的源点当成一个“超级源点”问题就变成了单源最短路问题。
1. 01矩阵中等
以所有的0为源点开始BFS。
距离数组dist最开始全部初始化为-1表示没有被访问过后续要修改成距离步数。所以首先我们不用创建visited数组标记坐标有没有被访问过其次不用创建step变量记录步数并且不用计算本层坐标点的个数count也就是说不用确定坐标点是在第几层。
class Solution {
public:vectorvectorint updateMatrix(vectorvectorint mat) {int m mat.size();int n mat[0].size();vectorvectorint dist(m, vectorint(n, -1)); // 全部初始化为-1// 坐标上下左右的偏移量int dr[4] { -1,1,0,0 };int dc[4] { 0,0,-1,1 };queuepairint, int q;// 所有的源点入队并修改距离为0for (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 [row, col] q.front();q.pop();// 判断刚才出队的坐标上下左右是否满足条件满足条件则入队并修改距离for (int j 0; j 4; j){int r row dr[j];int c col dc[j];if (r 0 r m c 0 c n dist[r][c] -1){q.push({r, c});dist[r][c] dist[row][col] 1;}}}return dist;}
};
2. 地图中的最高点中等
水域格子的值是确定的为0以所有的0为源点开始BFS和上一题“01矩阵”一模一样。
class Solution {
public:vectorvectorint highestPeak(vectorvectorint isWater) {int m isWater.size();int n isWater[0].size();vectorvectorint dist(m, vectorint(n, -1)); // 全部初始化为-1// 坐标上下左右的偏移量int dr[4] { -1,1,0,0 };int dc[4] { 0,0,-1,1 };queuepairint, int q;// 所有的源点入队并修改距离为0for (int i 0; i m; i){for (int j 0; j n; j){if (isWater[i][j] 1){q.push({i, j});dist[i][j] 0;}}}while (!q.empty()){// 队头出队auto [row, col] q.front();q.pop();// 判断刚才出队的坐标上下左右是否满足条件满足条件则入队并修改距离for (int j 0; j 4; j){int r row dr[j];int c col dc[j];if (r 0 r m c 0 c n dist[r][c] -1){q.push({r, c});dist[r][c] dist[row][col] 1;}}}return dist;}
};
3. 地图分析中等
以所有的陆地单元格为源点开始BFS陆地单元格对应在距离数组dist中的值为0和“01矩阵”、“地图中的最高点”都是一样的题。
class Solution {
public:int maxDistance(vectorvectorint grid) {int m grid.size();int n grid[0].size();vectorvectorint dist(m, vectorint(n, -1)); // 全部初始化为-1int ans -1;// 坐标上下左右的偏移量int dr[4] { -1,1,0,0 };int dc[4] { 0,0,-1,1 };queuepairint, int q;// 所有的源点入队并修改距离为0for (int i 0; i m; i){for (int j 0; j n; j){if (grid[i][j] 1){q.push({i, j});dist[i][j] 0;}}}while (!q.empty()){// 队头出队auto [row, col] q.front();q.pop();// 判断刚才出队的坐标上下左右是否满足条件满足条件则入队并修改距离for (int j 0; j 4; j){int r row dr[j];int c col dc[j];if (r 0 r m c 0 c n dist[r][c] -1){q.push({r, c});dist[r][c] dist[row][col] 1;ans max(ans, dist[r][c]);}}}return ans;}
};
