目录
- 一、边权为1的最短路问题
- 二、迷宫中离入口最近的出口
- 三、最小基因变化
- 四、单词接龙
- 五、为高尔夫比赛砍树
一、边权为1的最短路问题
如图：从A到I，怎样走路径最短
- 一个队列+一个哈希表
- 队列：一层一层递进，直到目的地为止
- 哈希表：记录当前位置是否经过，经过的就不用再进队列
- 为什么可以使用BFS？因为每条边的长度为1，同样的速率走，走相同的步频，谁先到目的地，谁的路径就是最短的
二、迷宫中离入口最近的出口
题目：
思路：BFS+哈希表 找最短路径
- 能到边界，返回ret，ret是层数
- 不能到边界，队列层序结束，返回-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(vector<vector<char>>& maze, vector<int>& entrance) {
int n = maze.size();
int m = maze[0].size();
int ret = 0;
queue<pair<int, 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 i=0; i<4; i++)
{
int x2 = x1+bx[i];
int y2 = y1+by[i];
if(x2>=0&&x2<n&&y2>=0&&y2<m&&maze[x2][y2]=='.'&&!hash[x2][y2])
{
if(x2==0 || x2==n-1 || y2==0 || y2==m-1)
{
return ret;
}
q.push({x2, y2});
}
}
// 标记经过的位置 更新队列
hash[x1][y1] = true;
q.pop();
}
}
return -1;
}
};
三、最小基因变化
题目：
题目理解：
- 一次变化相当于步数，所以可以用BFS
- 最终要变化成的基因序列必须是基因库中存在的，否则返回-1
- 每一次的变化，也必须是在基因库中存在的，否则返回-1
思路：BFS+哈希表
- 两个哈希表，一个标记基因库中有的基因序列，后续要使用（判断每次变化是否在基因库中）；另一个标记是否已经出现过，防止重复
- start字符串与end字符串相同，直接返回0
- end字符串不在基因库中，直接返回-1
- BFS：一个队列，层序遍历，一层就是一次变化
- 基因序列如何变化？题目是字符串有8个字符，所以每个位置的字符变化一次，变化的字符有4个：ACGT
- 只要在基因库中存在并且没有出现过，就入队列，如果该字符串与end字符串相同，就直接返回ret
- 细节：变化前（内循环外面），先用一个临时字符串代替，这样保证只修改了一次；否则变化到后面，前面的也都变化了，就不止修改了一次
- 队列层序完，没有end字符串等于tmp(变化的字符串)，就说明start字符串变化不到end字符串，最终返回-1
代码：
class Solution {
public:
int minMutation(string startGene, string endGene, vector<string>& bank) {
unordered_map<string, int> hash; // 标记基因库中出现过的
for(auto &e : bank) hash[e]++;
unordered_map<string, int> vis; // 标记每次变化是否出现过 防止重复
// 如果刚开始就相同
if(startGene == endGene) return 0;
// endGene不在基因库中
if(hash[endGene] == 0) return -1;
// 变化的字符
string change = "ACGT";
queue<string> 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 i=0; i<8; i++)
{
string tmp = t;// 临时的，保证只修改一次
for(int j=0; j<4; 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，即返回ret+1
代码：
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_map<string, int> hash;
for(auto &e : wordList) hash[e]++;
unordered_map<string, int> vis;
if(beginWord == endWord) return 0;
if(hash[endWord] == 0) return 0;
// 要变化的字符
string str;
for (auto& e : wordList)
{
str += e;
}
set<char> se(str.begin(), str.end());
string change(se.begin(), se.end());//
queue<string> 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 i=0; i<wordList[0].size(); i++)
{
string tmp = t;
for(int j=0; j<change.size(); j++)
{
tmp[i] = change[j];
if(hash[tmp] > 0 && vis[tmp] == 0)
{
q.push(tmp);
if(tmp == endWord)
{
return ret+1;
}
}
}
}
}
}
return 0;
}
};
五、为高尔夫比赛砍树
题目：
思路：BFS+哈希表
- 把二维数组中所有大于1的元素排序，每次找的元素根据排序从小到大，如上图所示，找一次相当于找一个树的最短路径，所以本题等价于多个迷宫找出口
- 注意：是要找最小的树，然后再根据顺序往上找其他树，并不是说一定要从1开始找，因为1是地面，只是上面的栗子刚好起始点就是1；如果1和4交换，千万不能从4开始走到1，再去找2，这是错的；【0，0】是4，或者说不管是多少，直接去找最小的树就行了（上面的栗子最小的树是2）；如果【0，0】起始点就是最小的树，也不影响，代码中有加判断跳过，然后找次小的树(次小的树这时变成最小的树)，剩下找的过程是正常的（总之：开始找最小的树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(vector<vector<int>>& forest) {
if(forest[gx][gy] == 0) return -1;
n = forest.size();
m = forest[0].size();
vector<int> v;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; 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(vector<vector<int>>& forest, int tar)
{
if(tar == forest[gx][gy])// 要找的树就是当前位置
{
return;
}
// 不是全局的，每次层序要更新(找一个树)
bool vis[50][50] = {false};
queue<pair<int, 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 i=0;i<4;i++)
{
int x2 = x1+bx[i];
int y2 = y1+by[i];
if(x2>=0&&x2<n&&y2>=0&&y2<m&&forest[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;
}
};