本专栏内容为：算法学习专栏，分为优选算法专栏，贪心算法专栏，动态规划专栏以及递归，搜索与回溯算法专栏四部分。 通过本专栏的深入学习，你可以了解并掌握算法。
💓博主csdn个人主页：小小unicorn
⏩专栏分类：算法从入门到精通
🚚代码仓库：小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识
专题十六
- 最小基因变化
- 算法原理
- 单词接龙
- 算法原理：
- 为高尔夫比赛砍树
- 算法原理：
最小基因变化
题目来源：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;
}
};
