仿织梦长沙网站公司,房子如何上网站做民宿,广告公关公司,如何做网站首页图目录 一、边权为1的最短路问题二、迷宫中离入口最近的出口三、最小基因变化四、单词接龙五、为高尔夫比赛砍树 一、边权为1的最短路问题 如图#xff1a;从A到I#xff0c;怎样走路径最短
一个队列一个哈希表队列#xff1a;一层一层递进#xff0c;直到目的地为止哈希表从A到I怎样走路径最短
一个队列一个哈希表队列一层一层递进直到目的地为止哈希表记录当前位置是否经过经过的就不用再进队列为什么可以使用BFS因为每条边的长度为1同样的速率走走相同的步频谁先到目的地谁的路径就是最短的
二、迷宫中离入口最近的出口
题目 思路BFS哈希表 找最短路径
能到边界返回retret是层数不能到边界队列层序结束返回-1必须是某个位置的上下左右为边界才符合条件即使刚开始就在边界也不行也必须要移动移动到另一个边界上才算否则队列循环结束也是返回-1参考示例2和示例3
代码
class Solution {
public:int bx[4] {-1,1,0,0};int by[4] {0,0,-1,1};bool hash[100][100] {false};int nearestExit(vectorvectorchar maze, vectorint entrance) {int n maze.size();int m maze[0].size();int ret 0;queuepairint, int q;q.push({entrance[0], entrance[1]});while(!q.empty()){int k q.size();ret;// 一层的个数while(k--){int x1 q.front().first;int y1 q.front().second;// 防止重复if(hash[x1][y1]){q.pop();continue;}for(int i0; i4; i){int x2 x1bx[i];int y2 y1by[i];if(x20x2ny20y2mmaze[x2][y2].!hash[x2][y2]){if(x20 || x2n-1 || y20 || y2m-1){return ret;}q.push({x2, y2});}}// 标记经过的位置 更新队列hash[x1][y1] true;q.pop();}}return -1;}
};三、最小基因变化
题目 题目理解
一次变化相当于步数所以可以用BFS最终要变化成的基因序列必须是基因库中存在的否则返回-1每一次的变化也必须是在基因库中存在的否则返回-1
思路BFS哈希表
两个哈希表一个标记基因库中有的基因序列后续要使用判断每次变化是否在基因库中另一个标记是否已经出现过防止重复start字符串与end字符串相同直接返回0end字符串不在基因库中直接返回-1BFS一个队列层序遍历一层就是一次变化基因序列如何变化题目是字符串有8个字符所以每个位置的字符变化一次变化的字符有4个ACGT只要在基因库中存在并且没有出现过就入队列如果该字符串与end字符串相同就直接返回ret细节变化前内循环外面先用一个临时字符串代替这样保证只修改了一次否则变化到后面前面的也都变化了就不止修改了一次队列层序完没有end字符串等于tmp(变化的字符串)就说明start字符串变化不到end字符串最终返回-1 代码
class Solution {
public:int minMutation(string startGene, string endGene, vectorstring bank) {unordered_mapstring, int hash; // 标记基因库中出现过的for(auto e : bank) hash[e];unordered_mapstring, int vis; // 标记每次变化是否出现过 防止重复// 如果刚开始就相同if(startGene endGene) return 0;// endGene不在基因库中if(hash[endGene] 0) return -1;// 变化的字符string change ACGT;queuestring q;int ret 0; // 层数就是变化次数q.push(startGene);while(!q.empty()){int k q.size();ret;while(k--){string t q.front();// 获取队列头vis[t];// 标记已经出现q.pop();// 删除for(int i0; i8; i){string tmp t;// 临时的保证只修改一次for(int j0; j4; j){tmp[i] change[j];// 对应位置修改// 在基因库中存在并且还没出现过if(hash[tmp] 0 vis[tmp] 0){q.push(tmp);// 等于最终的字符串 返回if(tmp endGene){return ret;}}}}}}return -1;}
};四、单词接龙
题目
思路BFS哈希表
本题与上题思路和过程几乎相同字符》字符串。以下是不同的地方要注意都是一次改变改变的是字符串中的一个字符上题是ACGT本题是wordList中出现的单词的所有字符记得要去重。接下来是用队列完成层序遍历与上题几乎一样不同点取队头元素时要判断它是否出现过出现过了就删除队头元素然后continue注意其实加这个是为了避免重复计算本题如果少了这个条件会超时上题没有加这个条件并没有超时因为wordList中每个单词的长度是一样的所以外循环是单词的长度在上题是固定的为8的字符内循环是要变化的字符的个数就是change字符串(set去重后的)上题是固定的ACGT为4个字符。其他是一样的。返回值不符合条件是返回0符合条件是返回单词接龙的长度不是层数单词接龙的长度就是层数1即返回ret1
代码
class Solution {
public:int ladderLength(string beginWord, string endWord, vectorstring wordList) {unordered_mapstring, int hash;for(auto e : wordList) hash[e];unordered_mapstring, int vis;if(beginWord endWord) return 0;if(hash[endWord] 0) return 0;// 要变化的字符string str;for (auto e : wordList){str e;}setchar se(str.begin(), str.end());string change(se.begin(), se.end());//queuestring q;int ret 0;q.push(beginWord);while(!q.empty()){int k q.size();ret;while(k--){string t q.front();if(vis[t] 0){q.pop();continue;}vis[t];q.pop();for(int i0; iwordList[0].size(); i){string tmp t;for(int j0; jchange.size(); j){tmp[i] change[j];if(hash[tmp] 0 vis[tmp] 0){q.push(tmp);if(tmp endWord){return ret1;}} }}}}return 0;}
};五、为高尔夫比赛砍树
题目 思路BFS哈希表
把二维数组中所有大于1的元素排序每次找的元素根据排序从小到大如上图所示找一次相当于找一个树的最短路径所以本题等价于多个迷宫找出口注意是要找最小的树然后再根据顺序往上找其他树并不是说一定要从1开始找因为1是地面只是上面的栗子刚好起始点就是1如果1和4交换千万不能从4开始走到1再去找2这是错的【00】是4或者说不管是多少直接去找最小的树就行了上面的栗子最小的树是2如果【00】起始点就是最小的树也不影响代码中有加判断跳过然后找次小的树(次小的树这时变成最小的树)剩下找的过程是正常的总之开始找最小的树ret开始计算最后flag的处理问题只要有走到目标树就不会经过最后的flag如果有经过最后的flag说明无路可走周围都是围墙这时就有可能还有树没有砍掉结果返回-1但是有一个情况例外当只剩下一个树了那它周围也就没有树了会经过flag可是这种情况是对的不能当作错误的情况处理可以加个条件下标i 等于gsz时代表是最后一个树不进入flag的处理
代码
class Solution {
public: int ret 0;// 返回值-步数int flag 0;// 标记-是否将所有的树砍掉int n, m;// 矩阵行列int gx 0, gy 0;// 开始的位置后面会更新int i 0;// 下标-从小到大int gsz 0;// 树的个数int bx[4] {-1,1,0,0};int by[4] {0,0,-1,1};int cutOffTree(vectorvectorint forest) {if(forest[gx][gy] 0) return -1;n forest.size();m forest[0].size();vectorint v;for(int i0; in; i){for(int j0; jm; j){if(forest[i][j] 1)// 找树{v.push_back(forest[i][j]);}}}sort(v.begin(), v.end());// 从最小的树开始或者找到最小树int sz v.size();gsz sz;// 全局的树的个数while(sz--){bfs(forest, v[i]);if(flag 1) return -1;// 还有树没有砍完i;// 到下一个树}return ret;}void bfs(vectorvectorint forest, int tar){if(tar forest[gx][gy])// 要找的树就是当前位置{return;}// 不是全局的每次层序要更新(找一个树)bool vis[50][50] {false};queuepairint, int q;q.push({gx, gy});while(!q.empty()){int k q.size();ret;while(k--){int x1 q.front().first;int y1 q.front().second;if(vis[x1][y1])// 防止重复{q.pop();continue;}q.pop();vis[x1][y1] true;for(int i0;i4;i){int x2 x1bx[i];int y2 y1by[i];if(x20x2ny20y2mforest[x2][y2]!0!vis[x2][y2]){q.push({x2, y2});// 找到目标树if(forest[x2][y2] tar){gx x2;// 更新下次就是从该位置开始gy y2;return;}}}}}if(i ! gsz-1) // 最后一个flag 1;}
};
