html5学习网站,广州快速建站哪家服务专业,建设银行佛山分行网站,网站建设的必要性’目录 1. 最短路问题介绍2. 算法原理和代码实现(含题目链接)1926.迷宫中离入口最近的出口433.最小基因变化127.单词接龙675.为高尔夫比赛砍树 3. 算法总结 1. 最短路问题介绍
最短路径问题是图论中的一类十分重要的问题。本篇文章只介绍边权为1(或边权相同)的最简单的最短路径问… 目录 1. 最短路问题介绍2. 算法原理和代码实现(含题目链接)1926.迷宫中离入口最近的出口433.最小基因变化127.单词接龙675.为高尔夫比赛砍树 3. 算法总结 1. 最短路问题介绍
最短路径问题是图论中的一类十分重要的问题。本篇文章只介绍边权为1(或边权相同)的最简单的最短路径问题。所谓边权就是两点之间的距离。 这类问题通俗的说就是告诉你起点和终点要你找出最短的路径或是最短路径是多少。 解决方法从起点开始来一次bfs即可。 A出队列后向外扩展一层BC入队列注意此时出队列要BC同时出(其实是写一个for循环先B后C)。 那如何计算出最短路径是多少呢 扩展的层数就是最短路的长度。
2. 算法原理和代码实现(含题目链接)
1926.迷宫中离入口最近的出口 算法原理 我们可以从起点开始层序遍历并且在遍历的过程中记录当前遍历的层数。这样就能在找到出⼝的时候得到起点到出⼝的最短距离。 把题目抽象为从当前位置出发到离边界上的那个点的最短路程是多少。 细节/技巧问题
(1) 人当前所在位置不能当做出口。 (2) 出口与边界相邻的空格就是出口。 (3) 人在移动时仅需走到出口位置即可不需要走出迷宫。
代码实现
class Solution
{int dx[4] {0,0,1,-1};int dy[4] {1,-1,0,0};public:int nearestExit(vectorvectorchar maze, vectorint e) {int m maze.size(), n maze[0].size();bool vis[m][n];memset(vis, 0, sizeof(vis));queuepairint, int q;q.push({e[0], e[1]});vis[e[0]][e[1]] true;int step 0; // 记录步数while(q.size()){step;int sz q.size();// 假设进去sz个要同时出for(int i 0; i sz; i){auto[a,b] q.front();q.pop();for(int j 0; j 4; j){int x adx[j], y bdy[j];if(x 0 x m y 0 y n maze[x][y] . !vis[x][y]){// 判断是否到达出口了if(x 0 || x m-1 || y 0 || y n-1)return step;else{q.push({x, y});vis[x][y] true;}}}}}return -1;}
};433.最小基因变化 算法原理 如果将每次字符串的变换抽象成图中的两个点和⼀条边的话问题就变成了边权为1的最短路题。 其他细节/技巧问题
(1) 原字符串每个字符变化后一定存在相同的此时要用哈希表来标记搜索的状态每次变化后都扔进哈希表中。 (2) 如何枚举出所有的变化情况呢直接两层for循环。 (3) 变化成哪种字符串才能入队列呢变化后的字符串在基因库中存在时才队列。所以把基因库里的字符串扔进哈希表中每次变化后都要判断是否在基因库中。
代码实现
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;if(!hash.count(endGene)) return -1;queuestring q;q.push(startGene);vis.insert(startGene);string change AGCT;int ret 0; //记录变化次数while(q.size()){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;}
};127.单词接龙 算法原理 这道题和第二题基本一模一样都是把一个字符串变化成目标字符串唯一不同的是本题统计的是整个过程中单词的个数其实就是上一题的最小次数1。 细节/技巧问题
参考前两题
代码实现
class Solution
{
public:int ladderLength(string beginWord, string endWord, vectorstring wordList) {unordered_setstring hash(wordList.begin(), wordList.end());unordered_setstring vis; // 标记已经搜索过的//if(beginWord endWord) return 1;if(!hash.count(endWord)) return 0;queuestring q;q.push(beginWord);vis.insert(beginWord);int ret 0;while(q.size()){ret;int sz q.size();while(sz--){string t q.front();q.pop();for(int i 0; i 10; i){string tmp t;for(char ch a; ch z; ch){tmp[i] ch; // 每次只修改一个字符// 存在列表中并且没有被访问过if(!vis.count(tmp) hash.count(tmp)){if(tmp endWord) return ret1; q.push(tmp);vis.insert(tmp);}}}}}return 0;}
};675.为高尔夫比赛砍树 算法原理 这道题目确实很难。 这道题可以抽象成若干个迷宫问题。我们只要计算出从这一棵树到下一棵树的最少步数再把所有的步数相加就可以求出砍完所有树的最少步数。所以这里要多次使用bfs算法写成函数它的作用是统计两棵树之间的最少步数。 难点/细节/技巧问题
(1) 树的坐标如何存储。使用vector容器。 (2) 由于要按照高度从低到高开始砍所以先要把树的高度排升序。 (3) bfs的参数是传起点和终点。
代码实现
class Solution
{int m, n;int dx[4] {0,0,1,-1};int dy[4] {1,-1,0,0};public:int cutOffTree(vectorvectorint f) {m f.size(), n f[0].size();// 记录树的位置vectorpairint, int trees;for(int i 0; i m; i)for(int j 0; j n; j)if(f[i][j] 1) trees.push_back({i, j}); // 是树才记录坐标// 从低到高开始砍sort(trees.begin(), trees.end(), [](const pairint, int p1,const pairint, int p2){return f[p1.first][p1.second] f[p2.first][p2.second];});int bx 0, by 0; // 起始位置int step 0;for(auto [a,b] : trees){// 使用bfs计算两树之间的最短路int ret bfs(f, bx, by, a, b);if(ret -1) return -1;step ret;bx a, by b; // 更新下一个位置的坐标}return step;}bool vis[51][51];int bfs(vectorvectorint f, int bx, int by, int ex, int ey){if(bx ex by ey) return 0;memset(vis, 0, sizeof(vis)); // 每次计算都要把标记还原queuepairint ,int q;q.push({bx, by});vis[bx][by] true;int ret 0; // 记录每两颗树之间的最短步数while(q.size()){ret;int sz q.size();while(sz--){auto[a, b] q.front();q.pop();for(int k 0; k 4; k){int x adx[k], y bdy[k];if(x 0 x m y 0 y n !vis[x][y] f[x][y]){// 判断是否走到终点if(x ex y ey) return ret;q.push({x, y});vis[x][y] true;}}}}return -1;}
};3. 算法总结 bfs算法是解决最短路问题的经典方法。我感觉解决最短路问题核心的关键是每一次出队列时都要把上一次入队列的数据全部出完(就要写for循环)而最短路程就是向外扩展的层数。
