【算法笔记】7.LeetCode-Hot100-图论专项

本来按照 Hot100 的顺序，刷了二叉树，但是由于编辑器糟糕的设计，导致文稿丢失，先写下一节图论。

刷题过半，发觉没必要掌握所有方法，只要掌握一种自己能理解的题解思路就可以。很多题解很没意思，纯粹以丧失可读性为代价优化复杂度，不如先找一种能稳定解题的方法再说。

1. 岛屿数量

如果发现一格是陆地，以它为基准，向上下左右进行广度优先搜索，如果是陆地，转换成水域(0)。

class Solution {
public:int numIslands(vector<vector<char>>& grid) {int nr = grid.size(); // 行数if (!nr) return 0;    // 如果网格为空，直接返回0int 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;      // 标记有新橘子腐烂}}}// 如果有新橘子腐烂，时间加1if (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 后可以学 coursebeforeCount[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); // 这门课可以学了}}}// 如果全部课程都能完成，返回 truereturn studied == numCourses;}
};

4. 实现 Trie (前缀树)

应用题，如果不用智能指针，需要注意内存泄露问题。

#include <string>
using namespace std;class Trie {
private:// 每个节点最多有 26 个小写字母子节点struct TrieNode {TrieNode* children[26] = {}; // 初始化为 nullptrbool 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~25if (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;}
};