目录
一、1926. 迷宫中离入口最近的出口 - 力扣（LeetCode）
算法代码：
代码分析
各个部分的解释
注意事项
整体的含义
具体情况
使用 e[0] 和 e[1] 的优势
总结
示例代码中的用法
整体流程
示例
复杂度分析
总结
二、433. 最小基因变化 - 力扣（LeetCode）
算法代码：
代码逻辑思路
数据结构准备
边界条件检查
广度优先搜索（BFS）初始化
BFS 主循环
返回结果
总结
三、127. 单词接龙 - 力扣（LeetCode）
算法代码：
代码逻辑思路
数据结构准备
边界条件检查
BFS 初始化
BFS 主循环
返回结果
关键点总结
广度优先搜索（BFS）
字母替换的生成
访问标记
复杂度分析
四、675. 为高尔夫比赛砍树 - 力扣（LeetCode）
算法代码：
代码逻辑思路
数据结构和变量初始化
步骤一：收集树的位置并排序
步骤二：依次砍树
BFS 函数
关键点总结
边界条件的处理
复杂度分析
一、1926. 迷宫中离入口最近的出口 - 力扣（LeetCode）
算法代码：
class Solution {
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
public:
int nearestExit(vector<vector<char>>& maze, vector<int>& e) {
int m = maze.size(), n = maze[0].size();
bool vis[m][n];
memset(vis, 0, sizeof vis);
queue<pair<int, int>> q;
q.push({e[0], e[1]});
vis[e[0]][e[1]] = true;
int step = 0;
while (q.size()) {
step++;
int sz = q.size();
for (int i = 0; i < sz; i++) {
auto [a, b] = q.front();
q.pop();
for (int j = 0; j < 4; j++) {
int x = a + dx[j], y = b + dy[j];
if (x >= 0 && x < m && y >= 0 && y < n &&
maze[x][y] == '.' && !vis[x][y]) {
// 判断是否已经到达出⼝
if (x == 0 || x == m - 1 || y == 0 || y == n - 1)
return step;
q.push({x, y});
vis[x][y] = true;
}
}
}
}
return -1;
}
};代码分析
-
类声明和成员变量：
class Solution { int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0};-
dx和dy数组用于表示四个方向的移动。dx和dy分别表示水平方向和垂直方向的增量，方向分别是右、左、下、上。
-
-
公共成员函数：
public: int nearestExit(vector<vector<char>>& maze, vector<int>& e) { int m = maze.size(), n = maze[0].size(); bool vis[m][n]; memset(vis, 0, sizeof vis); queue<pair<int, int>> q; q.push({e[0], e[1]}); vis[e[0]][e[1]] = true; int step = 0;-
m和n分别是迷宫的行数和列数。 -
vis是一个二维数组，用来记录每个位置是否已访问过，防止重复访问。 -
q是一个队列，用于广度优先搜索。队列存储的是坐标对(a, b)，表示当前位置。 -
初始时，将入口位置
e[0], e[1]入队，并将其标记为已访问。 -
memset(vis, 0, sizeof vis);是 C 和 C++ 中的一个函数调用，主要用于初始化数组或内存区域。具体来说，这个语句的含义如下：各个部分的解释
-
memset函数：-
memset是一个标准库函数，定义在<cstring>头文件中。它的作用是将指定内存区域的内容设置为某个值。 -
函数原型如下：
void* memset(void* ptr, int value, size_t num); -
其中
ptr是要设置的内存区域的起始地址，value是要设置的值，num是要设置的字节数。
-
-
vis：-
在这段代码中，
vis是一个二维布尔数组，用于记录在迷宫中每个位置是否已被访问过。在此上下文中，vis数组通常是用来避免重复访问同一位置。
-
-
0：-
这里的
0表示将vis数组的所有元素设置为0。在布尔数组中，0通常被视为false，这意味着在初始化时，所有位置都被标记为未访问。
-
-
sizeof vis：-
sizeof vis获取vis数组所占的字节数。这样，memset会将整个数组的内存区域都设置为0。
-
-
假设
vis是一个 2D 数组，大小为5 x 5，初始状态可能是未定义的。通过memset初始化后，vis将变成：vis = { {false, false, false, false, false}, {false, false, false, false, false}, {false, false, false, false, false}, {false, false, false, false, false}, {false, false, false, false, false} };注意事项
-
memset只适用于简单类型的数组，如int、char和bool等，因为它是按字节设置的。对于包含复杂类型（如类对象或结构体）的数组，通常应使用构造函数或相应的初始化方法。 -
对于
bool类型的数组，使用memset进行初始化是可以的，因为0会被解释为false。但是，在处理其他类型（如int、float等）时，要确保理解0的含义。 -
整体的含义
因此，
memset(vis, 0, sizeof vis);的作用是将整个vis数组的所有元素初始化为false（或0），以表明在开始搜索之前，所有位置都未被访问过。这对于 BFS 或 DFS 等算法是非常重要的，因为我们需要跟踪哪些位置已经被访问，以避免无限循环和多次访问同一位置。 -
在给定的代码中，入口位置使用
e[0]和e[1]表示的原因是因为e是一个向量（或数组），通常用于存储二维空间中的坐标。具体来说，e表示入口点的坐标，通常形式如下： -
e[0]表示行索引（即纵坐标）。 -
e[1]表示列索引（即横坐标）。 -
具体情况
在这段代码中，
e是一个vector<int>类型的变量，用来存储迷宫中入口的坐标。例如，如果入口位置为(2, 3)，则可以表示为e的内容如下：vector<int> e = {2, 3}; // e[0] = 2 (行), e[1] = 3 (列)使用
e[0]和e[1]的优势 -
清晰的语义：
-
使用
e[0]和e[1]来表示入口位置的行和列，可以让代码更加清晰易懂。读者可以很容易地理解e[0]是行坐标，e[1]是列坐标。
-
-
简洁性：
-
将入口位置封装在一个数组或向量中，使得在参数传递和处理时可以更简洁。例如，函数可以直接接受
vector<int>& e而不是两个单独的整数参数，这样可以减少函数参数的数量，并保持相关数据的整合。
-
-
灵活性：
-
如果需要扩展功能，比如处理多入口或不同的坐标系统，可以很方便地调整
e的结构，而不需要更改函数签名或大量代码。
-
-
这里使用
e[0]和e[1]将入口的坐标放入队列中以进行后续的搜索。总结
使用
e[0]和e[1]表示入口位置的行和列索引是一个常见且有效的做法。这种方式将坐标封装在数组中，不仅提高了代码的可读性和可维护性，也为后续的扩展和修改提供了便利。示例代码中的用法
在给定的代码中，入口位置
e被用于初始化 BFS 的起始点，例如：q.push({e[0], e[1]});
-
-
广度优先搜索（BFS）：
while (q.size()) { step++; // 每经过一层，步数加1 int sz = q.size(); // 当前队列的大小，即当前层的节点数 for (int i = 0; i < sz; i++) { auto [a, b] = q.front(); // 获取队头元素 q.pop(); for (int j = 0; j < 4; j++) { // 遍历四个方向 int x = a + dx[j], y = b + dy[j]; if (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.' && !vis[x][y]) { // 判断是否已经到达出口 if (x == 0 || x == m - 1 || y == 0 || y == n - 1) return step; q.push({x, y}); // 将该位置加入队列 vis[x][y] = true; // 标记该位置为已访问 } } } } return -1; // 如果队列为空，说明没有出口，返回-1-
外层
while循环通过队列进行层级遍历（即 BFS）。 -
每次处理一层节点，
step记录当前的步数。 -
内层循环对当前节点的四个方向进行探索，检查新位置是否符合条件：
-
是否在迷宫的边界上。
-
是否是可走的位置（
maze[x][y] == '.'）。 -
是否未被访问过（
!vis[x][y]）。
-
-
如果找到迷宫边界上的出口，则返回当前步数
step。 -
如果没有找到出口，则将当前合法位置入队，并标记为已访问。
-
-
函数返回：
-
如果遍历完所有可能的路径都没有找到出口，返回
-1，表示无法到达出口。
-
整体流程
-
从入口点开始，广度优先搜索每一层的所有可达点。
-
在搜索过程中，如果到达迷宫的边界（表示是一个出口），返回当前步数。
-
如果搜索完所有点都没有找到出口，返回
-1。
示例
假设输入的迷宫是：
maze = {
{'+', '+', '+', '+', '+', '+'},
{'+', '.', '.', '.', '.', '+'},
{'+', '.', '#', '#', '#', '+'},
{'+', '.', '#', '.', '#', '+'},
{'+', '.', '.', '.', 'E', '+'},
{'+', '+', '+', '+', '+', '+'}
};
e = {1, 1}; // 入口位置
-
初始时，入口位置是
(1, 1)。 -
广度优先搜索会检查四个方向，并在找到
E（出口）时返回当前步数。
复杂度分析
-
时间复杂度：O(m * n)，其中 m 和 n 是迷宫的行数和列数。最坏情况下，我们需要遍历每个点一次。
-
空间复杂度：O(m * n)，用于存储访问标记数组
vis和队列q。
总结
这段代码使用广度优先搜索（BFS）算法解决了从入口到达最近出口的问题，适用于迷宫类的最短路径问题。通过逐层扩展搜索范围，确保找到了最短路径。
二、433. 最小基因变化 - 力扣（LeetCode）
算法代码：
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; // 如果起始和目标基因相同，返回 0
if (!hash.count(endGene))
return -1; // 如果目标基因不在基因库，返回 -1
// BFS 初始化
queue<string> q;
q.push(startGene);
vis.insert(startGene);
int ret = 0; // 当前变异步数
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]; // 进行替换
// 检查新的基因是否在 bank 中且未被访问过
if (hash.count(tmp) && !vis.count(tmp)) {
if (tmp == endGene)
return ret; // 如果找到了目标基因，返回步数
q.push(tmp); // 否则入队
vis.insert(tmp); // 标记已访问
}
}
}
}
}
return -1; // 如果遍历完没有找到目标基因，返回 -1
}
};
代码逻辑思路
-
数据结构准备
-
使用
unordered_set<string> vis来记录已经访问过的基因序列，以避免重复搜索。 -
使用
unordered_set<string> hash来存储基因库中的所有基因序列，以便快速查找。 -
定义一个字符串
change，表示可以变异的基因字符（即 "A", "C", "G", "T"）。
-
-
边界条件检查
-
如果
startGene等于endGene，说明已经在目标基因上，返回0。 -
如果
endGene不在hash中，说明无法到达目标，返回-1。
-
-
广度优先搜索（BFS）初始化
-
使用一个队列
queue<string> q，将startGene入队，表示从此基因开始进行变异。 -
将
startGene标记为已访问。
-
-
BFS 主循环
-
使用一个
while循环，直到队列为空。 -
在每一层中，记录当前队列的大小
sz，表示当前变异的步数。 -
对于队列中的每个基因序列：
-
生成它的所有可能变异序列。
-
通过外层循环遍历序列的每一个位置（总共 8 个基因）。
-
对于每个基因位置，使用内层循环遍历变异字符（"A", "C", "G", "T"）。
-
生成新的基因序列
tmp，如果tmp在基因库中且未被访问：-
如果
tmp等于endGene，返回当前的变异步数ret。 -
否则，将
tmp入队，并标记为已访问。
-
-
-
-
返回结果
-
如果 BFS 结束时仍未找到
endGene，返回-1，表示无法达到目标基因。
-
总结
-
广度优先搜索（BFS）：使用 BFS 可以确保找到最短路径，因为它逐层扩展搜索的范围，保证了找到目标基因的最小变异步数。
-
边界条件：在处理字符串变异问题时，确保对边界情况进行适当处理。
这种方法有效且简洁，可以用于解决类似的最短路径或状态转移问题。
三、127. 单词接龙 - 力扣（LeetCode）
算法代码：
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; // 不在返回0
queue<string> q; // 初始化队列
q.push(beginWord); // 将起始单词入队
vis.insert(beginWord); // 标记起始单词为已访问
int ret = 1; // 变换步数初始化为1
while (q.size()) { // BFS循环
ret++; // 每次进入新的层，步数加1
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 (hash.count(tmp) && !vis.count(tmp)) {
if (tmp == endWord) // 如果找到了目标单词，返回步数
return ret;
q.push(tmp); // 否则入队
vis.insert(tmp); // 标记为已访问
}
}
}
}
}
return 0; // 如果遍历完没有找到目标单词，返回0
}
};
代码逻辑思路
-
数据结构准备
-
使用
unordered_set<string> hash来快速存储和查找单词列表中的单词。 -
使用
unordered_set<string> vis来标记已经访问过的单词，防止重复搜索。 -
使用一个队列
queue<string> q来实现广度优先搜索（BFS），用于按层遍历单词。
-
-
边界条件检查
-
如果
endWord不在单词列表hash中，返回0，表示无法到达目标单词。
-
-
BFS 初始化
-
将
beginWord入队，并标记为已访问。 -
初始化步数
ret为1，表示当前的变换步骤。
-
-
BFS 主循环
-
使用一个
while循环，当队列不为空时进行搜索。 -
在每一层中，增加步数
ret，记录当前层的大小sz。 -
遍历当前层的单词，根据每个单词生成可能的变换单词：
-
对于每个字母的位置，尝试用 ‘a’ 到 ‘z’ 的每个字符进行替换，生成新的单词
tmp。 -
如果
tmp在hash中且未被访问：-
如果
tmp等于endWord，返回当前的变换步数ret。 -
否则，将
tmp入队，并标记为已访问。
-
-
-
-
返回结果
-
如果 BFS 遍历结束仍未找到
endWord，返回0，表示无法达到目标单词。
-
关键点总结
-
广度优先搜索（BFS）
-
BFS 是解决最短路径问题的经典方法，确保找到最少的变换步数。
-
-
字母替换的生成
-
通过遍历每个字母位置，并尝试替换为 ‘a’ 到 ‘z’ 的每个字符来生成新的单词。
-
-
访问标记
-
使用
unordered_set<string> vis来避免重复处理同一个单词，从而提高效率。
-
-
复杂度分析
-
时间复杂度为 O(N * M * 26)，其中 N 是单词列表的大小，M 是单词的长度。每个单词最多有 M 个位置可以更换，且每个位置有 26 种可能的字符。
-
空间复杂度为 O(N)，用于存储单词集合和访问标记。
-
这种方法有效且高效，可以解决类似的单词接龙问题。
四、675. 为高尔夫比赛砍树 - 力扣（LeetCode）
算法代码：
class Solution {
int m, n;
public:
int cutOffTree(vector<vector<int>>& f) {
m = f.size(), n = f[0].size();
// 1. 准备工作：找出砍树的顺序
vector<pair<int, int>> trees;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (f[i][j] > 1)
trees.push_back({i, j});
// 根据树的高度排序
sort(trees.begin(), trees.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] : trees) {
int step = bfs(f, bx, by, a, b);
if (step == -1)
return -1; // 如果无法到达
ret += step; // 累加到总步数
bx = a, by = b; // 更新当前位置
}
return ret; // 返回总步数
}
bool vis[51][51]; // 访问标记
int dx[4] = {0, 0, 1, -1}; // 方向数组
int dy[4] = {1, -1, 0, 0}; // 方向数组
int bfs(vector<vector<int>>& f, int bx, int by, int ex, int ey) {
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; // 如果没有找到目标树，返回 -1
}
};
-
代码逻辑思路
-
数据结构和变量初始化
-
m和n分别表示网格的行数和列数。 -
trees用于存储所有树的位置（坐标），并在后续进行排序。 -
bx和by是当前的位置（开始时，通常设定为(0, 0)），ret用于累积总步数。
-
-
步骤一：收集树的位置并排序
-
遍历整个网格
f，找到所有树的位置（即f[i][j] > 1），并将它们以(i, j)的形式存储在trees中。 -
使用
std::sort对trees进行排序，按照树的高度进行升序排列。排序的比较函数使用了 Lambda 表达式。
-
-
步骤二：依次砍树
-
遍历排序后的
trees，对于每棵树，调用bfs函数计算从当前的位置到目标树的步数。 -
如果
bfs返回-1，说明无法到达这棵树，直接返回-1。 -
如果可以到达，则将步数累加到
ret，并更新当前位置为当前树的位置。
-
-
BFS 函数
-
该函数负责计算从当前坐标到目标树坐标的最短路径。
-
如果当前坐标与目标树坐标相同，直接返回
0步。 -
使用队列
q进行广度优先搜索，使用数组vis记录已访问的位置。 -
在每一步中，遍历四个可能的方向（上、下、左、右），如果当前坐标是有效的且未被访问且不是障碍，入队并标记为已访问。
-
如果在某一步找到了目标树坐标，返回当前步数。
-
如果队列为空且尚未找到目标，返回
-1。
-
关键点总结
-
数据结构和算法
-
使用
std::vector存储树的位置并进行排序。 -
BFS 用于寻找从一个点到另一个点的最短路径，适合用于路径搜索问题。
-
-
边界条件的处理
-
对于不能到达的树，直接返回
-1。
-
-
复杂度分析
-
时间复杂度：
-
找树的位置：O(m * n)
-
排序树的位置：O(k log k)，其中 k 是树的数量。
-
BFS 搜索：每次从起点到树的搜索复杂度为 O(m * n)。
-
-
空间复杂度：O(m * n)，主要用于存储访问标记和队列。
-
这种方法可以有效地解决树木砍伐的最小路径问题，确保路径的有效性和优化。
-
![[数据结构]双链表详解](https://i-blog.csdnimg.cn/direct/f8f3ec43c4e4434e8d5dd42b949da564.png)
