最小基因变化
题目来源：Leetcode433.最小基因变化
基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 ‘A’、‘C’、‘G’ 和 ‘T’ 之一。
假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
例如，“AACCGGTT” --> “AACCGGTA” 就是一次基因变化。
另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）
给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。
注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。
算法原理
本题目首先可以进行转化：
->转化为图论问题中的边权为1的最短路问题。
根据基因变换只能变换一个，我们把每一个基因抽象成一个点，那么这个问题就可以转化为：已知起点位置和终点位置，从起点位置到终止位置的最短路径，由于每次只能变换一个字母，所以边权都为1。
分析到这，解题思路就是用BFS。
但是在写代码前，还需注意一下细节：
- 为防止有的遍历重复，我们需要用一个数组来进行标记，但是普通数组显然不能满足需求，因为存的是字符串，所以我们应用哈希表进行储存。
- 如何枚举出所有的情况呢？
答案很简单，我们暴力枚举一下字符串即可。 - 枚举出的所以情况，都需要加入到队列里么？
答案是不需要，因为本身存在一个基因库，在枚举字符串中，在基因库中我们才进入队列。 - 如何快速判断在基因库中存在？
普通做法就是直接遍历整个基因库，但是这样还是显得太麻烦，我们可以先预处理一下，直接将基因库丢在哈希中，在哈希表中进行查找，方便快速加快效率。
代码实现：
class Solution { public: int minMutation(string startGene, string endGene, vector<string>& bank) { //用来标记是否是已经搜索过的状态 unordered_set<string> vis; unordered_set<string> hash(bank.begin(),bank.end());//存储基因库中里面的字符串 string change="ACGT"; //处理边界情况 if(startGene==endGene) return 0; int ret=0; queue<string> q; q.push(startGene); vis.insert(startGene); 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; } };
单词接龙
题目来源：108.单词接龙
在字典（单词列表） wordList 中，从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：
序列中第一个单词是 beginWord 。
序列中最后一个单词是 endWord 。
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典 wordList 中的单词。
给定两个长度相同但内容不同的单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。
算法原理：
分析一遍，其实本题跟最小基因库基本是一样的，只是本题的问法不一样：
本题问的是个数，所以我们要再返回层数的基础上加1.
代码实现：
class Solution { public: int ladderLength(string beginWord, string endWord, vector<string>& wordList) { //存储单词列表 unordered_set<string> hash(wordList.begin(),wordList.end()); unordered_set<string> vis;//标记已经搜索过的单词 //判断边界情况 if(!hash.count(endWord)) return 0; queue<string> q; q.push(beginWord); vis.insert(beginWord); //因为返回的是个数，所以初始化可以初始化为1 int ret=1; while(q.size()) { 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 ch='a';ch<='z';ch++) { tmp[i]=ch; if(!vis.count(tmp)&&hash.count(tmp)) { if(tmp==endWord) return ret; q.push(tmp); vis.insert(tmp); } } } } } return 0; } };
为高尔夫比赛砍树
题目来源：Leetcode675.为高尔夫比赛砍树
你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中：
0 表示障碍，无法触碰
1 表示地面，可以行走
比 1 大的数 表示有树的单元格，可以行走，数值表示树的高度
每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。
你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。
你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。
可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。
算法原理：
本题首先也可以转化：
可以看这个例子：
根据砍树由低到高，我们可以把砍树的顺序弄出来：
然后我们让每一段的路径都最小，那么总和肯定也就最小。
那么这个问题就可以转化为我们之前做过的迷宫问题。
而本题是若干个迷宫问题。
还记的什么是迷宫问题吗？
迷宫问题从起始点位置到边界情况下的最短路径，此题是前一个位置到后一个位置的最短路径。
问题解决到这，那么我们又怎么知道砍树顺序呢？
这时就需要用到我们的容器，我们用一个二维数组存储，可以是哈希可以是vector只要能将里面进行排序，那么我们就可以拿来用。
代码解决：
class Solution { int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; public: int cutOffTree(vector<vector<int>>& f) { // int m = f.size(), n= f[0].size(); //1.准备工作，找出砍树的顺序 vector<pair<int,int>> tree; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(f[i][j]>1) tree.push_back({i,j}); } } //排序 sort(tree.begin(),tree.end(),[&](const pair<int,int>&p1,const pair<int,int>&p2) { return f[p1.first][p1.second]<f[p2.first][p2.second]; }); //2.按照顺序砍树 int bx=0,by=0; int ret=0; for(auto& [a,b]:tree) { int step=bfs(f,bx,by,a,b); if(step==-1) return -1; ret+=step; bx=a,by=b; } return ret; } //3.bfs bool vis[51][51]; int bfs(vector<vector<int>>& f,int bx,int by,int ex,int ey) { int m = f.size(), n= f[0].size(); if(bx==ex&&by==ey) return 0; queue<pair<int,int>> q; //清空之前数据 memset(vis,0,sizeof vis); q.push({bx,by}); vis[bx][by]=true; int step=0; while(q.size()) { 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&&f[x][y]&&!vis[x][y]) { if(x==ex&&y==ey) return step; q.push({x,y}); vis[x][y]=true; } } } } return -1; } };
