手机网站开发技术,南阳网站推广效果,网页源代码里哪个是视频链接,优质的聊城网站建设算法沉淀——BFS 解决最短路问题#xff08;leetcode真题剖析#xff09; 01.迷宫中离入口最近的出口02.最小基因变化03.单词接龙04.为高尔夫比赛砍树 BFS#xff08;广度优先搜索#xff09;是解决最短路径问题的一种常见算法。在这种情况下#xff0c;我们通常使用BFS来… 算法沉淀——BFS 解决最短路问题leetcode真题剖析 01.迷宫中离入口最近的出口02.最小基因变化03.单词接龙04.为高尔夫比赛砍树 BFS广度优先搜索是解决最短路径问题的一种常见算法。在这种情况下我们通常使用BFS来查找从一个起始点到目标点的最短路径。 具体步骤如下
初始化 从起始点开始将其放入队列中并标记为已访问。BFS遍历 不断从队列中取出顶点然后探索与该顶点相邻且未被访问的顶点。对于每个相邻顶点将其标记为已访问并将其加入队列。这样每一轮BFS都会探索到当前距离起始点的步数更多的顶点。重复步骤2 重复这个过程直到找到目标点或者队列为空。路径重建可选 如果需要找到实际的路径而不仅仅是路径的长度通常在BFS的过程中维护一个记录每个顶点是由哪个顶点发现的信息然后通过回溯从目标点追溯到起始点重建路径。
BFS的优势在于它保证首次到达目标点的路径就是最短路径因为在BFS的遍历过程中我们首次访问一个顶点时它是离起始点最近的未访问顶点之一。
这种算法广泛应用于图的最短路径问题例如在无权图中寻找最短路径或者在有权图中权值为1的情况下寻找最少步数的路径。
01.迷宫中离入口最近的出口
题目链接https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/
给你一个 m x n 的迷宫矩阵 maze 下标从 0 开始矩阵中有空格子用 . 表示和墙用 表示。同时给你迷宫的入口 entrance 用 entrance [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
每一步操作你可以往 上下左 或者 右 移动一个格子。你不能进入墙所在的格子你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。
请你返回从 entrance 到最近出口的最短路径的 步数 如果不存在这样的路径请你返回 -1 。
示例 1
输入maze [[,,.,],[.,.,.,],[,,,.]], entrance [1,2]
输出1
解释总共有 3 个出口分别位于 (1,0)(0,2) 和 (2,3) 。
一开始你在入口格子 (1,2) 处。
- 你可以往左移动 2 步到达 (1,0) 。
- 你可以往上移动 1 步到达 (0,2) 。
从入口处没法到达 (2,3) 。
所以最近的出口是 (0,2) 距离为 1 步。示例 2
输入maze [[,,],[.,.,.],[,,]], entrance [1,0]
输出2
解释迷宫中只有 1 个出口在 (1,2) 处。
(1,0) 不算出口因为它是入口格子。
初始时你在入口与格子 (1,0) 处。
- 你可以往右移动 2 步到达 (1,2) 处。
所以最近的出口为 (1,2) 距离为 2 步。示例 3
输入maze [[.,]], entrance [0,0]
输出-1
解释这个迷宫中没有出口。提示
maze.length mmaze[i].length n1 m, n 100maze[i][j] 要么是 . 要么是 。entrance.length 20 entrancerow m0 entrancecol nentrance 一定是空格子。
思路
这是属于图论中边路权值为1的情况利用层序遍历来解决迷宫问题是最经典的做法。我们可以从起点开始层序遍历并且在遍历的过程中记录当前遍历的层数。这样就能在找到出口的时候得到起点到出口的最短距离。
代码
class Solution {const int dx[4]{0,0,1,-1};const int dy[4]{-1,1,0,0};public:int nearestExit(vectorvectorchar maze, vectorint entrance) {queuepairint,int q;int mmaze.size(),nmaze[0].size();int visit[m][n];memset(visit,0,sizeof visit);int step0;q.push({entrance[0],entrance[1]});visit[entrance[0]][entrance[1]]1;while(!q.empty()){step;int szq.size();for(int i0;isz;i){auto [a,b]q.front();q.pop();for(int k0;k4;k){int xadx[k],ybdy[k];if(x0xmy0ynmaze[x][y].!visit[x][y]){if(x0||xm-1||y0||yn-1) return step;q.push({x,y});visit[x][y]1;}}}}return -1;}
};定义了常量数组 dx 和 dy 表示上下左右四个方向。使用 BFS 进行迷宫遍历。使用队列 q 存储当前需要遍历的点使用数组 visit 记录是否访问过。将入口点入队并标记为已访问。在每一步中从队列中取出当前层次的所有点并尝试在四个方向上扩展。如果扩展到边界说明找到了最近的出口返回步数。如果队列为空仍未找到说明无法找到出口返回 -1。
02.最小基因变化
题目链接https://leetcode.cn/problems/minimum-genetic-mutation/
基因序列可以表示为一条由 8 个字符组成的字符串其中每个字符都是 A、C、G 和 T 之一。
假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
例如AACCGGTT -- AACCGGTA 就是一次基因变化。
另有一个基因库 bank 记录了所有有效的基因变化只有基因库中的基因才是有效的基因序列。变化后的基因必须位于基因库 bank 中
给你两个基因序列 start 和 end 以及一个基因库 bank 请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化返回 -1 。
注意起始基因序列 start 默认是有效的但是它并不一定会出现在基因库中。
示例 1
输入start AACCGGTT, end AACCGGTA, bank [AACCGGTA]
输出1示例 2
输入start AACCGGTT, end AAACGGTA, bank [AACCGGTA,AACCGCTA,AAACGGTA]
输出2示例 3
输入start AAAAACCC, end AACCCCCC, bank [AAAACCCC,AAACCCCC,AACCCCCC]
输出3 提示
start.length 8end.length 80 bank.length 10bank[i].length 8start、end 和 bank[i] 仅由字符 [A, C, G, T] 组成
思路
其实这也可以直接转化成边路权值为1的图论问题。具体思路是
使用哈希集合 hash 存储基因库便于快速查询某个基因是否合法。使用广度优先搜索BFS从起始基因开始不断变异基因直到找到目标基因为止。在每一步中对当前基因的每个位置尝试变异成可能的字符如果变异后的基因是合法的且未被访问过就加入队列中并标记为已访问。如果队列为空仍未找到目标基因返回-1表示无法变异到目标基因。如果找到目标基因返回步数
代码
class Solution {
public:int minMutation(string startGene, string endGene, vectorstring bank) {unordered_setstring vis; // 用于记录已经访问过的基因序列unordered_setstring hash(bank.begin(), bank.end()); // 将基因库放入哈希集合中方便查询是否是合法基因if (startGene endGene) return 0; // 如果起始基因和目标基因相同不需要变异返回步数为0if (!hash.count(endGene)) return -1; // 如果目标基因不在基因库中无法变异到目标基因返回-1string change ACGT; // 可能的基因变异字符queuestring q;q.push(startGene);vis.insert(startGene);int ret 0;while (!q.empty()) {ret;int sz q.size();while (sz--) {string t q.front();q.pop();for (int i 0; i 8; i) {string tmp t;for (int j 0; j 4; j) {tmp[i] change[j]; // 尝试将当前位置的基因变异为可能的字符if (hash.count(tmp) !vis.count(tmp)) { // 如果变异后的基因是合法的且未被访问过if (tmp endGene) return ret; // 如果变异后的基因与目标基因相同返回步数q.push(tmp);vis.insert(tmp); // 标记为已访问}}}}}return -1; // 如果队列为空仍未找到目标基因说明无法变异到目标基因返回-1}
};03.单词接龙
题目链接https://leetcode.cn/problems/word-ladder/
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord - s1 - s2 - ... - sk
每一对相邻的单词只差一个字母。对于 1 i k 时每个 si 都在 wordList 中。注意 beginWord 不需要在 wordList 中。sk endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList 返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列返回 0 。
示例 1
输入beginWord hit, endWord cog, wordList [hot,dot,dog,lot,log,cog]
输出5
解释一个最短转换序列是 hit - hot - dot - dog - cog, 返回它的长度 5。示例 2
输入beginWord hit, endWord cog, wordList [hot,dot,dog,lot,log]
输出0
解释endWord cog 不在字典中所以无法进行转换。 提示
1 beginWord.length 10endWord.length beginWord.length1 wordList.length 5000wordList[i].length beginWord.lengthbeginWord、endWord 和 wordList[i] 由小写英文字母组成beginWord ! endWordwordList 中的所有字符串 互不相同
思路
其实这道困难题和上面的题思路基本一致只不过变化范围扩大到了26个小写字母还有返回值的计算。
使用哈希集合 hash 存储单词列表便于快速查询某个单词是否合法。使用广度优先搜索BFS从起始单词开始不断替换单词的每个位置的字符直到找到目标单词为止。在每一步中对当前单词的每个位置尝试替换成可能的字符如果替换后的单词是合法的且未被访问过就加入队列中并标记为已访问。如果队列为空仍未找到目标单词返回0表示无法接龙到目标单词。如果找到目标单词返回步数。
代码
class Solution {
public:int ladderLength(string beginWord, string endWord, vectorstring wordList) {unordered_setstring vis; // 用于记录已经访问过的单词unordered_setstring hash(wordList.begin(), wordList.end()); // 将单词列表放入哈希集合中方便查询是否是合法单词if (beginWord endWord) return 1; // 如果起始单词和目标单词相同不需要接龙返回步数为1if (!hash.count(endWord)) return 0; // 如果目标单词不在单词列表中无法接龙到目标单词返回0int ret 1;queuestring q;q.push(beginWord);vis.insert(beginWord);while (!q.empty()) {ret;int sz q.size();while (sz--) {string t q.front();q.pop();for (int i 0; i t.size(); i) {string tmp t;for (char c a; c z; c) {tmp[i] c; // 尝试将当前位置的字符替换为可能的字符if (hash.count(tmp) !vis.count(tmp)) { // 如果替换后的单词是合法的且未被访问过if (tmp endWord) return ret; // 如果替换后的单词与目标单词相同返回步数q.push(tmp);vis.insert(tmp); // 标记为已访问}}}}}return 0; // 如果队列为空仍未找到目标单词说明无法接龙到目标单词返回0}
};04.为高尔夫比赛砍树
题目链接https://leetcode.cn/problems/cut-off-trees-for-golf-event/
你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示 在这个矩阵中
0 表示障碍无法触碰1 表示地面可以行走比 1 大的数 表示有树的单元格可以行走数值表示树的高度
每一步你都可以向上、下、左、右四个方向之一移动一个单位如果你站的地方有一棵树那么你可以决定是否要砍倒它。
你需要按照树的高度从低向高砍掉所有的树每砍过一颗树该单元格的值变为 1即变为地面。
你将从 (0, 0) 点开始工作返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树返回 -1 。
可以保证的是没有两棵树的高度是相同的并且你至少需要砍倒一棵树。
示例 1
输入forest [[1,2,3],[0,0,4],[7,6,5]]
输出6
解释沿着上面的路径你可以用 6 步按从最矮到最高的顺序砍掉这些树。示例 2
输入forest [[1,2,3],[0,0,0],[7,6,5]]
输出-1
解释由于中间一行被障碍阻塞无法访问最下面一行中的树。示例 3
输入forest [[2,3,4],[0,0,5],[8,7,6]]
输出6
解释可以按与示例 1 相同的路径来砍掉所有的树。
(0,0) 位置的树可以直接砍去不用算步数。提示
m forest.lengthn forest[i].length1 m, n 500 forest[i][j] 109
思路
这里和之前的题不一样的地方是我们每次都要找到最矮的树依次砍完所有的数所以我们要针对从小到大每颗数的相对位置进行BFS遍历计算步数。
遍历整个矩形森林将树木的位置加入 trees 数组中。根据树木的高度进行排序。遍历排好序的树木数组使用广度优先搜索BFS计算从当前位置 (bx, by) 到目标位置 (a, b) 的步数。如果无法到达目标位置返回 -1。累加步数并更新起始位置 (bx, by)。最终返回累加的步数作为结果。
代码
class Solution {const int dx[4] {0, 0, 1, -1};const int dy[4] {-1, 1, 0, 0};int m, n;int vis[51][51];int bfs(vectorvectorint forest, int bx, int by, int ex, int ey) {if (bx ex by ey) return 0; // 如果起始位置和目标位置相同步数为0queuepairint, int q;memset(vis, 0, sizeof vis);q.push({bx, by});vis[bx][by] 1;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], y b dy[i];if (x 0 x m y 0 y n forest[x][y] !vis[x][y]) {if (x ex y ey) return step; // 如果到达目标位置返回步数q.push({x, y});vis[x][y] 1; // 标记为已访问}}}}return -1; // 如果未能到达目标位置返回-1表示无法到达}public:int cutOffTree(vectorvectorint forest) {m forest.size(), n forest[0].size();vectorpairint, int trees;// 遍历整个矩形森林将树木的位置加入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 bx 0, by 0; // 起始位置为(0, 0)int ret 0;// 遍历排好序的树木数组for (auto [a, b] : trees) {// 使用BFS计算从当前位置到目标位置的步数int step bfs(forest, bx, by, a, b);if (step -1) return -1; // 如果无法到达目标位置返回-1ret step; // 累加步数bx a, by b; // 更新起始位置}return ret;}
};
