1. 岛屿数量
题目链接：岛屿数量
题目描述：给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
解答
方法一：深度优先
可以将二维网格看成一个无向图，竖直或水平相邻的 1 1 1 之间有边相连（利用图论知识）
为求出岛屿的数量，扫描整个二维网格。如果一个位置为 1 1 1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1 1 1 都会被重新标记为 0 0 0（因为这是属于一个岛屿的）。
最终岛屿的数量就是进行深度优先搜索的次数。(思路比较简单，代码编写也不是很难）
class Solution {
private:
void dfs(vector<vector<char>>& grid, int r, int c) {
int nr = grid.size();
int nc = grid[0].size();
grid[r][c] = '0';
if (r - 1 >= 0 && grid[r - 1][c] == '1') // 向左探测
dfs(grid, r - 1, c);
if (r + 1 < nr && grid[r + 1][c] == '1') // 向右探测
dfs(grid, r + 1, c);
if (c - 1 >= 0 && grid[r][c - 1] == '1') // 向上探测
dfs(grid, r, c - 1);
if (c + 1 < nc && grid[r][c + 1] == '1') // 向下探测
dfs(grid, r, c + 1);
}
public:
int numIslands(vector<vector<char>>& grid) {
int nr = grid.size(); // 记录网格的行数
if (!nr)
return 0;
int nc = grid[0].size(); // 记录网格的列数
int count_num_islands = 0; // 记录岛屿的数量
for (int row = 0; row < nr; row++) {
for (int col = 0; col < nc; col++) {
if (grid[row][col] == '1') {
count_num_islands++;
dfs(grid, row, col); // 深度优先，将同一个岛屿的1置成0
}
}
}
return count_num_islands; // 返回最终岛屿数量的结果
}
};
方法二：广度优先
思想也是类似于深度优先，为了求出岛屿的数量，扫描整个二维网格。如果一个位置为 1 1 1，则将其加入队列，开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 1 1 1 都会被重新标记为 0 0 0。直到队列为空（这个地方和深度优先类似，深度优先也是搜索到这个岛屿所涉及到的全部位置置成 0 0 0 ,才进行下一个岛屿的搜索），搜索结束。
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int nr = grid.size(); // 记录网格的行数
if (!nr)
return 0;
int nc = grid[0].size(); // 记录网格的列数
int count_num_island = 0; // 记录岛屿的数量
for (int row = 0; row < nr; row++) {
for (int col = 0; col < nc; col++) {
if (grid[row][col] == '1') {
++count_num_island;
grid[row][col] = '0'; // 对应网格位置数字置成 0
queue<pair<int, int>> neighbors; // 创建队列
neighbors.push({row, col}); // 当前网格的位置入队列
while (
!neighbors
.empty()) { // 也是类似于深度优先的思路，将该岛屿涉及到的位置全部置成0
auto rc = neighbors.front(); // 记录队列的第一个元素
neighbors.pop(); // 弹出队列的第一个元素
int r = rc.first, c = rc.second; // 双元素队列的相关操作
if (r - 1 >= 0 && grid[r - 1][c] == '1') {
neighbors.push({r - 1, c});
grid[r - 1][c] = '0';
}
if (r + 1 < nr && grid[r + 1][c] == '1') {
neighbors.push({r + 1, c});
grid[r + 1][c] = '0';
}
if (c - 1 >= 0 && grid[r][c - 1] == '1') {
neighbors.push({r, c - 1});
grid[r][c - 1] = '0';
}
if (c + 1 < nc && grid[r][c + 1] == '1') {
neighbors.push({r, c + 1});
grid[r][c + 1] = '0';
}
}
}
}
}
return count_num_island;
}
};
又或者写成下面的形式：
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.empty() || grid[0].empty())
return 0;
int nr = grid.size();
int nc = grid[0].size();
vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
int count_num_island = 0;
for (int row = 0; row < nr; row++) {
for (int col = 0; col < nc; col++) {
if (grid[row][col] == '1') {
++count_num_island;
grid[row][col] = '0'; // 标记已访问
queue<pair<int, int>> neighbors;
neighbors.push({row, col});
while (!neighbors.empty()) {
auto rc = neighbors.front();
neighbors.pop();
int r = rc.first;
int c = rc.second;
for (auto& dir : directions) {
int new_r = r + dir.first;
int new_c = c + dir.second;
if (new_r >= 0 && new_r < nr && new_c >= 0 &&
new_c < nc && grid[new_r][new_c] == '1') {
neighbors.push({new_r, new_c});
grid[new_r][new_c] = '0';
}
}
}
}
}
}
return count_num_island;
}
};
方法三：并查集
有关于并查集的相关介绍详见：并查集
凡是涉及到元素的分组管理问题，都可以考虑使用并查集进行维护。 而该题可以将不同的岛屿看成不同的组，然后对每个位置进行并查集判断是否属于某一个组即可。
思路如下：
为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1 1 1，则将其与相邻四个方向上的 1 1 1 在并查集中进行合并。
最终岛屿的数量就是并查集中连通分量的数目。
#include <vector>
#include <algorithm> // 用于 swap
using namespace std;
// 并查集（Union-Find）类，用于高效管理连通分量
class UnionFind {
private:
vector<int> parent; // parent[i] 表示节点 i 的父节点
vector<int> rank; // rank[i] 表示以 i 为根的树的“秩”（近似高度），用于优化合并操作
int count; // 当前连通分量（岛屿）的数量
public:
// 查找操作：找到节点 i 所在集合的根节点，并进行路径压缩
// 路径压缩：将查找路径上的所有节点直接连接到根节点，加快后续查找
int find(int i) {
// 如果 parent[i] == i，说明 i 是根节点，直接返回
// 否则递归查找父节点，并将 parent[i] 更新为根节点（路径压缩）
return parent[i] == i ? i : (parent[i] = find(parent[i]));
// 上述三元运算符表达式等价于下面的代码
// if (i == parent[i]) {
// return i;
// } else {
// parent[i] = find(parent[i]);
// return parent[i];
// }
}
// 合并操作：将包含 x 和 y 的两个集合合并为一个
void unite(int x, int y) {
int rootx = find(x); // 找到 x 所在集合的根
int rooty = find(y); // 找到 y 所在集合的根
// 如果根相同，说明已在同一集合，无需合并
if (rootx != rooty) {
// 按秩合并：将秩较小的树合并到秩较大的树下，以保持树的平衡
if (rank[rootx] < rank[rooty]) {
swap(rootx, rooty); // 保证 rootx 的秩 >= rooty 的秩
}
parent[rooty] = rootx; // 将 rooty 的根指向 rootx
// 如果两棵树的秩相等，合并后根节点的秩加 1
if (rank[rootx] == rank[rooty]) {
rank[rootx] ++;
}
// 成功合并两个不同集合，连通分量数量减一
--count;
}
}
// 获取当前连通分量的数量（即岛屿数量）
int getCount() const {
return count;
}
// 构造函数：初始化并查集
// grid 是输入的二维网格，'1' 表示陆地，'0' 表示水
UnionFind(vector<vector<char>>& grid) {
count = 0; // 初始化连通分量数量为 0
int m = grid.size();
int n = grid[0].size();
// 遍历整个网格，初始化 parent 和 rank 数组
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
// 如果是陆地，初始化其父节点为自身（表示独立的一个连通分量）
parent.push_back(i * n + j);
count++; // 每发现一个 '1'，连通分量数量加一
} else {
// 如果是水，用 -1 标记，表示无效节点
parent.push_back(-1);
}
// 初始化每个节点的秩为 0
rank.push_back(0);
}
}
}
};
// Solution 类：解决“岛屿数量”问题
class Solution {
public:
// 主函数：计算二维网格中岛屿的数量
// 岛屿由相邻的陆地（'1'）连接而成，相邻指上下左右四个方向
int numIslands(vector<vector<char>>& grid) {
int nr = grid.size(); // 行数
if (!nr) return 0; // 网格为空，返回 0
int nc = grid[0].size(); // 列数
// 创建并查集对象，自动初始化所有陆地节点为独立连通分量
UnionFind uf(grid);
// 遍历整个网格，对每个陆地节点，尝试与相邻的陆地节点合并
for (int r = 0; r < nr; r++) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
// 将当前陆地置为 '0'，防止重复访问（虽然并查集已处理，但此处是习惯性操作）
grid[r][c] = '0';
// 检查上方是否有陆地，如果有则合并
if (r - 1 >= 0 && grid[r - 1][c] == '1') {
uf.unite(r * nc + c, (r - 1) * nc + c);
}
// 检查下方是否有陆地，如果有则合并
if (r + 1 < nr && grid[r + 1][c] == '1') {
uf.unite(r * nc + c, (r + 1) * nc + c);
}
// 检查左方是否有陆地，如果有则合并
if (c - 1 >= 0 && grid[r][c - 1] == '1') {
uf.unite(r * nc + c, r * nc + c - 1);
}
// 检查右方是否有陆地，如果有则合并
if (c + 1 < nc && grid[r][c + 1] == '1') {
uf.unite(r * nc + c, r * nc + c + 1);
}
}
}
}
// 返回最终的连通分量数量，即岛屿数量
return uf.getCount();
}
};
不写 UnionFind 类的代码：
class Solution {
private:
vector<int> parent; // 并查集的父节点数组
vector<int> rank; // 用于按秩合并优化
int count; // 当前连通分量（岛屿）的数量
// 查找 + 路径压缩
int find(int x) {
return parent[x] == x ? x : (parent[x] = find(parent[x]));
}
// 合并两个集合（按秩合并）
void unite(int x, int y) {
int rootx = find(x);
int rooty = find(y);
if (rootx == rooty)
return;
if (rank[rootx] < rank[rooty]) {
swap(rootx, rooty);
}
parent[rooty] = rootx;
if (rank[rootx] == rank[rooty]) {
rank[rootx]++;
}
--count;
}
public:
int numIslands(vector<vector<char>>& grid) {
int nr = grid.size();
if (nr == 0)
return 0;
int nc = grid[0].size();
// 初始化并查集相关数据结构
parent.clear();
rank.clear();
count = 0;
// 映射二维坐标到一维：(r, c) -> r * nc + c
int total = nr * nc;
parent.resize(total);
rank.resize(total, 0); // 初始化 rank 为 0
// 遍历网格，初始化 parent 和 count
for (int i = 0; i < nr; ++i) {
for (int j = 0; j < nc; ++j) {
if (grid[i][j] == '1') {
parent[i * nc + j] = i * nc + j; // 自己是自己的父节点
count++; // 每个陆地初始为一个连通分量
} else {
parent[i * nc + j] = -1; // 水标记为 -1，表示无效
}
}
}
// 遍历每个格子，与上下左右的陆地合并
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] != '1')
continue;
int idx = r * nc + c;
// 检查四个方向的邻居
// 上
if (r > 0 && grid[r - 1][c] == '1') {
unite(idx, (r - 1) * nc + c);
}
// 下
if (r < nr - 1 && grid[r + 1][c] == '1') {
unite(idx, (r + 1) * nc + c);
}
// 左
if (c > 0 && grid[r][c - 1] == '1') {
unite(idx, r * nc + (c - 1));
}
// 右
if (c < nc - 1 && grid[r][c + 1] == '1') {
unite(idx, r * nc + (c + 1));
}
}
}
return count;
}
};
2. 腐烂的橘子
题目链接：腐烂的橘子
题目描述：在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
解答
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
queue<pair<int, int>> q;
int dirctions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 四个方向
int row = grid.size(); // 网格行数
int col = grid[0].size(); // 网格列数
int cnt = 0; // 记录新鲜橘子的数量
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == 2) {
q.push({i, j});
} else if (grid[i][j] == 1) {
cnt++;
}
}
}
// 没有腐烂橘子，有新鲜橘子，直接返回 -1 即可
if (q.empty() && cnt) {
return -1;
}
int ans = 0; // 传播的最小分钟数
while (!q.empty()) {
int t = q.size(); // 遍历同一时间感染的橘子
for (int k = 0; k < t; k++) {
pair<int, int> p = q.front();
q.pop();
for (auto direction : dirctions) {
int x = p.first + direction[0];
int y = p.second + direction[1];
if (x >= 0 && y >= 0 && x < row && y < col &&
grid[x][y] == 1) {
grid[x][y] = 2; // 新鲜橘子变腐烂
q.push({x, y});
cnt--; // 新鲜橘子减少
}
}
}
if (!q.empty()) // 如果当前轮有新感染的橘子，时间加一
ans++;
}
if (cnt) // 如果到此处还有没被感染的橘子，直接返回 -1 即可。
return -1;
return ans; // 最后没有新鲜橘子了，返回传播的最小分钟数
}
};
3. 课程表
题目链接：课程表
题目描述：你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
解答
方法一： 拓扑排序（BFS + 邻接表）
这道题学过数据结构的就会发现，这是很经典的图论中的拓扑排序问题。甚至我上课的时候老师也是举的课程学习这个例子。代码如下：
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> in_degree(numCourses, 0);
vector<vector<int>> graph(numCourses);
// 建图 + 计算入度
for (auto& pre : prerequisites) {
int course = pre[0];
int prerequisite = pre[1];
graph[prerequisite].push_back(course);
in_degree[course]++;
}
// 找出所有入度为 0 的节点加入队列
queue<int> q;
for (int i = 0; i < numCourses; i++) {
if (in_degree[i] == 0)
q.push(i);
}
int visited = 0; // 记录能访问的节点数
while (!q.empty()) {
int node = q.front();
q.pop();
visited++;
// 遍历所有由 node 指向的课程
for (int neighbor : graph[node]) {
in_degree[neighbor]--;
if (in_degree[neighbor] == 0) {
q.push(neighbor);
}
}
}
return visited == numCourses;
}
};
当然，除了使用邻接表之外，还可以使用邻接矩阵，但是我们老师讲过，在图结构中，尤其是在稀疏图（边数远小于节点数的平方），邻接矩阵比邻接表更高效。
方法二：拓扑排序（DFS + 邻接表）判断是否有环
定义三个状态：
0: 代表未访问1: 代表正在访问（在当前 DFS 路径中）2: 代表已访问，且无环
class Solution {
private:
vector<vector<int>> graph;
vector<int> visited;
bool dfs(int node) {
if (visited[node] == 1)
return false;
if (visited[node] == 2)
return true;
visited[node] = 1;
for (int neighbor : graph[node]) {
if (!dfs(neighbor))
return false;
}
visited[node] = 2;
return true;
}
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
graph.resize(numCourses);
visited.assign(numCourses, 0);
for (auto& pre : prerequisites) {
graph[pre[1]].push_back(pre[0]);
}
for (int i = 0; i < numCourses; i++) {
if (!dfs(i))
return false;
}
return true;
}
};
4. 实现 Trie (前缀树)
题目链接：实现 Trie (前缀树)
题目描述：Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
请你实现 Trie 类：
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
解答
// 定义一个名为 Trie 的类，用于实现前缀树（字典树）数据结构
class Trie {
private:
// 标记当前节点是否为一个完整单词的结尾
// 例如，如果插入了 "apple"，那么代表 'e' 的节点的 isEnd 将为 true
bool isEnd;
// 指针数组，用于指向当前节点的 26 个可能的子节点（对应 a-z 26 个小写字母）
// next[i] 表示从当前节点出发，通过字母 ('a' + i) 能到达的子节点
// 如果 next[i] 为 NULL，表示没有以该字母为边的子节点
Trie* next[26];
public:
// 构造函数：初始化一个新的 Trie 节点
Trie() {
isEnd = false; // 默认新节点不是任何单词的结尾
// 将 next 数组的所有指针初始化为 NULL（使用 memset 将内存块清零）
// 这样可以确保所有子节点初始都不存在
memset(next, 0, sizeof(next));
}
// 向 Trie 中插入一个单词
void insert(string word) {
Trie* node = this; // 从根节点开始
// 遍历单词中的每一个字符
for (char c : word) {
// 计算当前字符 c 对应的索引（'a' -> 0, 'b' -> 1, ..., 'z' -> 25）
int index = c - 'a';
// 如果当前节点没有指向字符 c 的子节点，则创建一个新的 Trie 节点
if (node->next[index] == NULL) {
node->next[index] = new Trie();
}
// 移动到下一个节点（即字符 c 对应的子节点）
node = node->next[index];
}
// 整个单词插入完成后，将最后一个字符对应的节点标记为单词结尾
node->isEnd = true;
}
// 在 Trie 中搜索一个完整的单词
// 如果单词存在且完整匹配，则返回 true；否则返回 false
bool search(string word) {
Trie* node = this; // 从根节点开始
// 遍历要搜索的单词中的每一个字符
for (char c : word) {
// 计算字符对应的索引
int index = c - 'a';
// 移动到对应的子节点
node = node->next[index];
// 如果在某一步，对应的子节点为 NULL，说明该路径不存在，即单词不存在
if (node == NULL) {
return false;
}
}
// 遍历完所有字符后，检查最后一个节点是否被标记为单词结尾
// 这是为了区分完整单词和仅是前缀的情况
// 例如，如果只插入了 "apple"，那么搜索 "app" 会到达一个节点，但其 isEnd 为 false，所以返回 false
return node->isEnd;
}
// 判断 Trie 中是否存在以给定前缀开头的单词
// 只要前缀路径存在，就返回 true
bool startsWith(string prefix) {
Trie* node = this; // 从根节点开始
// 遍历前缀中的每一个字符
for (char c : prefix) {
// 计算字符对应的索引
int index = c - 'a';
// 移动到对应的子节点
node = node->next[index];
// 如果在某一步，对应的子节点为 NULL，说明没有单词以该前缀开头
if (node == NULL) {
return false;
}
}
// 如果成功遍历完前缀的所有字符，说明存在以该前缀开头的单词（至少有一个）
return true;
}
};
/**
* 使用示例和说明：
*
* // 创建一个 Trie 对象（根节点）
* Trie* obj = new Trie();
*
* // 插入一个单词到 Trie 中
* obj->insert("apple");
*
* // 搜索一个完整的单词，返回 true 或 false
* bool param_2 = obj->search("apple"); // 返回 true
* bool param_2b = obj->search("app"); // 返回 false（如果只插入了 "apple"）
*
* // 检查是否存在以某个字符串为前缀的单词，返回 true 或 false
* bool param_3 = obj->startsWith("app"); // 返回 true
*
* 注意：使用 new 创建的对象需要在适当的时候用 delete 手动释放内存，避免内存泄漏。
*/