LEETCODE HOT 100 图论 C‘s Log

核心特征题目中存在对象和它们之间的关系关系可以是相邻、感染、依赖、包含常见关键词“依赖/先决条件”有向图“连通/路径/能否到达”如岛屿数量上下左右相连的陆地构成一个整体“网络/关系/地图”实体是节点关系是边“网格上的扩散/蔓延”一句话总结问题抽象成“点”和“线”如何从一个点到另一个点或者点与点之间如何连接把整个二维网格想象成一片草地和湖泊1陆地是干枯的草地。0水是湖泊。2已访问是烧焦的地这里的dfs递归内部是遇到干枯草地就开始烧但是自己仍然站在原地直到火把连着的都烧完了接着开始移动访问的步伐这里包括水和烧焦的地但是每到一个干枯的草地再进行1的操作。整体的代码逻辑这样去理解更加形象深刻class Solution { private: void dfs(vectorvectorchar grid, int i, int j, int m, int n) { // 边界条件 // 出界或者当前不是陆地(1)返回 if (i 0 || i m || j 0 || j n || grid[i][j] ! 1) { return; } // 原地修改将 1 改为 2 grid[i][j] 2; dfs(grid, i, j - 1, m, n); // 左 dfs(grid, i, j 1, m, n); // 右 dfs(grid, i - 1, j, m, n); // 上 dfs(grid, i 1, j, m, n); // 下 } public: int numIslands(vectorvectorchar grid) { if (grid.empty()) return 0; int m grid.size(); int n grid[0].size(); int ans 0; for (int i 0; i m; i) { for (int j 0; j n; j) { // 发现一块新的陆地 if (grid[i][j] 1) { // 启动 DFS把这片岛屿全部“淹没” dfs(grid, i, j, m, n); ans; } } } return ans; } };994. 腐烂的橘子 - 力扣LeetCode僵尸危机之前的“火烧连营”看作是一个火种蔓延那么这道题的“腐烂橘子”就是多个火种同时蔓延初始状态有的橘子是健康的活人有的橘子天生就是僵尸2。扩散规则每过1 分钟所有现有的僵尸都会把它们身边的活人变成僵尸q数组就是当前这一批僵尸的坐标列表。nxt数组是用来收集下一分钟会变成僵尸的那些橘子。while循环每循环一次就代表过了一分钟。我们把q里的僵尸全部放出去咬人把咬到的新僵尸存进nxt然后时间ans。fresh变量是用来计数的“活人总数”。每当一个活人被咬活人总数就减 1。如果最后活人总数归零了说明病毒成功如果还有活人说明有活人躲在墙后面被 0 隔离了咬不到这里主要其实就是考虑一个每一次的进程的问题每一次都有哪些更新了每一次还剩什么class Solution { private: const int DIRECTIONS[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; public: int orangesRotting(vectorvectorint grid) { int m grid.size(); int n grid[0].size(); int fresh 0; // 统计新鲜橘子的总数 vectorpairint, int currentQueue; // 存储当前这一分钟所有腐烂的的坐标 for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { fresh; } else if (grid[i][j] 2) { // 初始的直接加入队列它们是第0分钟的扩散源 currentQueue.emplace_back(i, j); } } } int minutes 0; // 只有当还有新鲜橘子且还有腐烂橘子可以扩散时才继续循环 while (fresh 0 !currentQueue.empty()) { minutes; vectorpairint, int nextQueue; // 用来存储下一分钟新产生的腐烂橘子 // 遍历当前这一分钟所有的腐烂橘子 for (auto [x, y] : currentQueue) { // 检查四个方向 for (auto dir : DIRECTIONS) { int nx x dir[0]; int ny y dir[1]; // 边界检查 必须是新鲜橘子 if (nx 0 nx m ny 0 ny n grid[nx][ny] 1) { // 发现新鲜橘子 grid[nx][ny] 2; // 变成腐烂状态 fresh--; // 新鲜橘子数量减 1 nextQueue.emplace_back(nx, ny); // 加入下一分钟的队列 } } } // 一轮结束把“下一分钟的队列”赋值给“当前队列” currentQueue move(nextQueue); // 如果 nextQueue 是空的说明这一分钟没有产生腐烂 } // 如果 fresh 还大于 0说明有橘子被墙包围永远无法腐烂 if (fresh 0) { return -1; } return minutes; } };207. 课程表 - 力扣LeetCode在 DFS 查找环时我们不能只用“访问过/没访问过”两种状态因为这无法区分“死循环”和“正常分支fs函数中当你站在节点x看向邻居节点y时如果你看到y是灰色的1说明y正在被探索中。推论y是你的祖先节点是你这条搜索路径上更早的一环。结论你从y走到了x现在又发现了y找到了环如果你看到y是白色的0说明y没探索过如果你看到y是黑色的2说明y已经被彻底查过了证明从y出发是找不到环的。跳过“黑色” “已访问” “无环” “已回溯”class Solution { private: //图的邻接表 vectorvectorint graph; // 0: 白色(未访问), 1: 灰色(搜索中), 2: 黑色(已完成) vectorint colors; // 返回 true 代表找到了环 bool dfs(int x) { // 标记当前节点为“搜索中” colors[x] 1; // 遍历当前课程 x 的所有后续课程 y for (int y : graph[x]) { if (colors[y] 1) { // 绕了一圈又回到了 y return true; } if (colors[y] 0) { // 继续深搜 y if (dfs(y)) { return true; } } // colors[y] 2 (黑色) // y 已经完全搜索完毕且没环 } // x 及其所有后代都搜索完了且没发现环 colors[x] 2; // 标记为“已完成” return false; // 没找到环 } public: bool canFinish(int numCourses, vectorvectorint prerequisites) { graph.resize(numCourses); colors.resize(numCourses, 0); // 全部初始化为 0 // 将 prerequisites 转化为邻接表 // prerequisites[i] [a, b] 表示 b - a for (auto p : prerequisites) { int a p[0]; int b p[1]; graph[b].push_back(a); } // 检查每一个课程节点 for (int i 0; i numCourses; i) { // 如果该节点还没访问过就从它开始深搜 // 如果在任意一个连通分量中发现了环就返回 false if (colors[i] 0) { if (dfs(i)) { return false; // 发现了环无法完成课程 } } } // 所有节点都检查完了没发现环 return true; // 可以完成所有课程 } };208. 实现 Trie (前缀树) - 力扣LeetCodeTrie树就是一个巨大的字母迷宫root根节点是迷宫唯一的大门口Node节点是迷宫里的房间son[26]是每个房间里的26 扇门对应 a-zend标记是房间墙上的一面小红旗代表“这里是一个单词的终点”struct Node { Node* son[26]{}; // 26扇门初始都是关着的nullptr bool end false; // 初始没有红旗 };class Trie { Node* root new Node(); int find(string word) { Node* cur root; for (char c : word) {//拿着地图单词一个字母一个字母地走 c - a; // 把字母 a~z 变成数字 0~25对应门的编号 if (cur-son[c] nullptr) { // 发现前面的路断了 return 0; } cur cur-son[c];//路是通的穿过这扇门 } // 如果终点房间有红旗endtrue返回 2完全匹配 // 如果没红旗返回 1只是前缀不是完整单词 return cur-end ? 2 : 1; } void destroy(Node* node) { if (node nullptr) {// 没房间就跳过 return; } for (Node* son : node-son) {//子房间也得拆掉 destroy(son); } delete node; } public: ~Trie() { destroy(root); } void insert(string word) { Node* cur root; for (char c : word) {//逐个字母检查 c - a; if (cur-son[c] nullptr) { // 无路可走 cur-son[c] new Node(); // 暴力破墙修一扇新门建个新房间 } cur cur-son[c];// 穿过这扇门 } cur-end true;//单词走完了在最后一个房间插上一面红旗标记结束 } bool search(string word) { return find(word) 2;//我不仅要路通还必须是完整的单词。所以必须等于 2 } bool startsWith(string prefix) { return find(prefix) ! 0; } };