工程造价信息网查询,厦门seo网站推广优化,洛阳网站改版维护公司,网站建设优化工资高不目录 迷宫中离入口最近的出口
最小基因变化
单词接龙
为高尔夫比赛砍树 迷宫中离入口最近的出口
题目 思路
使用宽度优先遍历解决这道题#xff0c;需要一个二维数组标记是否被遍历过#xff0c;也需要一个队列辅助完成宽度优先遍历#xff0c;类似于水波纹一样#x…
目录 迷宫中离入口最近的出口
最小基因变化
单词接龙
为高尔夫比赛砍树 迷宫中离入口最近的出口
题目 思路
使用宽度优先遍历解决这道题需要一个二维数组标记是否被遍历过也需要一个队列辅助完成宽度优先遍历类似于水波纹一样一层一层的往外扩如果扩到了矩阵边缘行则返回步数就是离入口最近的距离。
代码
class Solution {int dx[4]{0,0,1,-1};int dy[4]{1,-1,0,0};public:int nearestExit(vectorvectorchar maze, vectorint entrance) {int mmaze.size(),nmaze[0].size();vectorvectorbool vis(m,vectorbool(n,false));queuepairint,int q;int step0;q.push({entrance[0],entrance[1]});vis[entrance[0]][entrance[1]]true;while(!q.empty()){int szq.size();step;for(int i0;isz;i){int aq.front().first;int bq.front().second;q.pop();for(int k0;k4;k){int xadx[k],ybdy[k];if(x0 xm y0 yn !vis[x][y] maze[x][y].){if(x0 || xm-1 || y0 || yn-1)return step;q.push({x,y});vis[x][y]true;}}}}return -1;}
};
最小基因变化
题目 思路
其实仔细分析这道题后可以发现也可以用宽度优先遍历来解决这道题每一次某位置变化一个字母就相当于以某位置为起点往外扩了一层为了便于快速地判断变换后的基因序列是否在基因库中将基因库中的基因序列存储到哈希表中同时也需要一个哈希表来标记某些基因序列是否已经变换过另外也需要一个队列来完成宽度优先遍历的辅助操作。
需要注意的是在对基因序列的某位置变换前需保存一下变换前的基因序列便于变换后再进行恢复还原。
代码
class Solution {
public:int minMutation(string startGene, string endGene, vectorstring bank) {unordered_setstring vis;unordered_setstring hash(bank.begin(),bank.end());string sACGT;if(startGeneendGene) return 0;if(!hash.count(endGene)) return -1;queuestring q;q.push(startGene);vis.insert(startGene);int ret0;while(!q.empty()){int szq.size();ret;for(int k0;ksz;k){string topq.front();q.pop();for(int i0;i8;i){string strtop;for(int j0;j4;j){top[i]s[j];if(topendGene) return ret;if(!vis.count(top) hash.count(top))q.push(top),vis.insert(top);}topstr;}}}return -1;}
};
单词接龙
题目 思路
其实这道题和前一道题是类似的只不过这道题的单词变化范围不再是A,C,G,T而是26个英文小写字母为了快速判断单词是否是字典中的单词首先将字典中的单词存放到哈希表中同时也需要一个哈希表标记已经访问过的单词和一个队列来完成宽度优先遍历的辅助操作。
这道题同上一道题一样进行单词的某位置前需要先保存原始单词以便变换完单词某位置后进行恢复和还原。
代码
class Solution {
public:int ladderLength(string beginWord, string endWord, vectorstring wordList) {unordered_setstring vis;unordered_setstring hash(wordList.begin(),wordList.end());if(!hash.count(endWord)) return 0;queuestring q;q.push(beginWord);vis.insert(beginWord);int ret1;while(!q.empty()){int szq.size();ret;for(int i0;isz;i){string topq.front();q.pop();for(int j0;jbeginWord.size();j){string strtop;for(char cha;chz;ch){top[j]ch;if(topendWord) return ret;if(!vis.count(top) hash.count(top))q.push(top),vis.insert(top);}topstr;}}}return 0;}
};
为高尔夫比赛砍树
题目 思路
解决这道题也是使用宽度优先遍历来解决但是题目要求按高度从低到高砍完所有的树因此需要对砍树的顺序进行排序然后求出被砍顺序挨着的两个树的最短距离分别求出这样的被砍顺序挨着的两个树的最短距离然后加起来就是按高度从低到高砍完所有树的最短步数如果某一步不能正常进行说明无法完成砍树直接返回-1.
代码
class Solution {int m,n;int dx[4]{1,-1,0,0};int dy[4]{0,0,1,-1};public:int cutOffTree(vectorvectorint forest) {mforest.size(),nforest[0].size();vectorpairint,int order;for(int i0;im;i)for(int j0;jn;j)if(forest[i][j]1)order.push_back({i,j});sort(order.begin(),order.end(),[](const pairint,int p1,const pairint,int p2){return forest[p1.first][p1.second]forest[p2.first][p2.second];});int bx0,by0;int ret0;for(auto [a,b]:order){int stepbfs(forest,bx,by,a,b);if(step-1) return -1;retstep;bxa,byb;}return ret;}int bfs(vectorvectorint forest,int bx,int by,int ex,int ey){if(bxex byey) return 0;queuepairint,int q;bool vis[51][51];memset(vis,false,sizeof vis);q.push({bx,by});vis[bx][by]true;int step0;while(!q.empty()){int szq.size();step;for(int i0;isz;i){auto [a,b]q.front();q.pop();for(int j0;j4;j){int xadx[j],ybdy[j];if(xex yey) return step;if(x0 xm y0 yn forest[x][y] !vis[x][y])q.push({x,y}),vis[x][y]true;}}}return -1;}
};
