本来按照 Hot100 的顺序，刷了二叉树，但是由于编辑器糟糕的设计，导致文稿丢失，先写下一节图论。
刷题过半，发觉没必要掌握所有方法，只要掌握一种自己能理解的题解思路就可以。很多题解很没意思，纯粹以丧失可读性为代价优化复杂度，不如先找一种能稳定解题的方法再说。
1. 岛屿数量
如果发现一格是陆地，以它为基准，向上下左右进行广度优先搜索，如果是陆地，转换成水域(0)。
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int nr = grid.size(); // 行数
if (!nr) return 0; // 如果网格为空，直接返回0
int nc = grid[0].size(); // 列数
int num_islands = 0; // 统计岛屿数量
// 遍历每个单元格
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
// 如果当前位置是陆地（'1'）
if (grid[r][c] == '1') {
num_islands++; // 找到一个新岛屿，计数加一
grid[r][c] = '0'; // 将其标记为访问过（变为水）
// 使用 BFS（广度优先搜索）探索整座岛屿
queue<pair<int, int>> neighbors;
neighbors.push({r, c}); // 将起始位置加入队列
while (!neighbors.empty()) {
pair<int, int> rc = neighbors.front(); // 获取当前坐标
neighbors.pop();
int row = rc.first, col = rc.second;
// 检查上方相邻单元格
if (row - 1 >= 0 && grid[row-1][col] == '1') {
neighbors.push({row-1, col});
grid[row-1][col] = '0'; // 标记访问
}
// 检查下方相邻单元格
if (row + 1 < nr && grid[row+1][col] == '1') {
neighbors.push({row+1, col});
grid[row+1][col] = '0';
}
// 检查左方相邻单元格
if (col - 1 >= 0 && grid[row][col-1] == '1') {
neighbors.push({row, col-1});
grid[row][col-1] = '0';
}
// 检查右方相邻单元格
if (col + 1 < nc && grid[row][col+1] == '1') {
neighbors.push({row, col+1});
grid[row][col+1] = '0';
}
}
}
}
}
return num_islands; // 返回最终统计的岛屿数量
}
};
2. 腐烂的橘子
和上题类似，用队列存储，用 BFS 做模拟。
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size(); // 网格的行数
int n = grid[0].size(); // 网格的列数
queue<pair<int, int>> q; // 用于BFS的队列，存放腐烂橘子的坐标
int fresh = 0; // 新鲜橘子的数量
// 预处理：统计新鲜橘子数量，并将所有腐烂橘子加入队列
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 2) {
q.emplace(i, j); // 腐烂橘子加入队列
} else if (grid[i][j] == 1) {
fresh++; // 统计新鲜橘子
}
}
}
// 如果没有新鲜橘子，直接返回 0 分钟
if (fresh == 0) return 0;
int minutes = 0;
vector<pair<int, int>> dirs = {{-1,0},{1,0},{0,-1},{0,1}}; // 上下左右四个方向
// BFS开始：每一轮表示一分钟
while (!q.empty()) {
int size = q.size(); // 当前分钟腐烂橘子的数量
bool rotted = false;
// 处理当前分钟所有腐烂橘子传播
for (int i = 0; i < size; ++i) {
auto [x, y] = q.front(); q.pop();
for (auto [dx, dy] : dirs) {
int nx = x + dx, ny = y + dy;
// 如果邻居是新鲜橘子，则腐烂它
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {
grid[nx][ny] = 2;
fresh--; // 新鲜橘子减少
q.emplace(nx, ny); // 新腐烂橘子加入下一轮处理
rotted = true; // 标记有新橘子腐烂
}
}
}
// 如果有新橘子腐烂，时间加1
if (rotted) minutes++;
}
// 如果还有剩余新鲜橘子，则说明不可能全部腐烂
return fresh == 0 ? minutes : -1;
}
};
3. 课程表
每门课程可能有一些“必须先学的课程”，先把所有“可以立刻学的课程”（没有前置课）放进一个队列里，然后一个一个学，如果某门课的所有前置课都完成了，就把它也加进队列。
最后如果所有课程都学完了，说明是可行的；否则，说明有互相依赖（死循环），学不了。
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
// 每门课程依赖哪些课程
vector<vector<int>> nextCourses(numCourses); // 记录某门课是哪些课的前置课程
vector<int> beforeCount(numCourses, 0); // 每门课需要完成的前置课程数量
// 建立依赖关系
for (auto& pre : prerequisites) {
int course = pre[0]; // 要学习的课程
int requirement = pre[1]; // 这门课程的前置课
nextCourses[requirement].push_back(course); // 学完 requirement 后可以学 course
beforeCount[course]++; // course 需要多一个前置课
}
queue<int> q; // 存放当前可以直接学习的课程（前置课数量为0）
for (int i = 0; i < numCourses; ++i) {
if (beforeCount[i] == 0) {
q.push(i); // 没有前置课程的课，先学
}
}
int studied = 0; // 记录已经完成的课程数量
while (!q.empty()) {
int current = q.front(); q.pop();
studied++; // 当前课程可以学，计数加一
// 学完 current 后，把它解锁的课程更新
for (int next : nextCourses[current]) {
beforeCount[next]--; // 有一门前置课已完成
if (beforeCount[next] == 0) {
q.push(next); // 这门课可以学了
}
}
}
// 如果全部课程都能完成，返回 true
return studied == numCourses;
}
};
- 实现 Trie (前缀树)
应用题，如果不用智能指针，需要注意内存泄露问题。
#include <string>
using namespace std;
class Trie {
private:
// 每个节点最多有 26 个小写字母子节点
struct TrieNode {
TrieNode* children[26] = {}; // 初始化为 nullptr
bool isEnd = false; // 是否是某个单词的结束位置
};
TrieNode* root;
public:
/** 初始化前缀树对象 */
Trie() {
root = new TrieNode();
}
/** 向前缀树中插入字符串 word */
void insert(string word) {
TrieNode* node = root;
for (char ch : word) {
int index = ch - 'a'; // 将字符映射到 0~25
if (node->children[index] == nullptr) {
node->children[index] = new TrieNode(); // 如果没有就创建节点
}
node = node->children[index]; // 向下移动
}
node->isEnd = true; // 标记这个节点为单词结尾
}
/** 如果字符串 word 在前缀树中，返回 true；否则，返回 false */
bool search(string word) {
TrieNode* node = root;
for (char ch : word) {
int index = ch - 'a';
if (node->children[index] == nullptr) return false;
node = node->children[index];
}
return node->isEnd; // 必须是单词结尾
}
/** 如果之前插入的字符串中，有以 prefix 为前缀的，返回 true；否则返回 false */
bool startsWith(string prefix) {
TrieNode* node = root;
for (char ch : prefix) {
int index = ch - 'a';
if (node->children[index] == nullptr) return false;
node = node->children[index];
}
return true; // 不要求结尾，只要路径存在
}
// 析构函数：释放内存
~Trie() {
destroy(root);
}
private:
// 递归释放所有节点
void destroy(TrieNode* node) {
if (node == nullptr) return;
for (int i = 0; i < 26; ++i) {
destroy(node->children[i]);
}
delete node;
}
};