LeetCode Hot 100 | 图论C 题解Hot100 图论200 / 994 / 207 / 208。目录LeetCode Hot 100 | 图论C 题解一、200. Number of Islands岛屿数量 中等题目描述图解解题思路C 代码二、994. Rotting Oranges腐烂的橘子 中等题目描述图解解题思路C 代码三、207. Course Schedule课程表 中等题目描述图解解题思路C 代码四、208. Implement Trie (Prefix Tree)实现 Trie 前缀树 中等题目描述图解解题思路C 代码总结一、200. Number of Islands岛屿数量 中等题目描述给你一个由1陆地和0水组成的二维网格请你计算网格中岛屿的数量。岛屿总是被水拦截并且每座岛屿只能由水平方向和/或垂直方向上相邻的陆地连接而成。示例 1输入grid [ [1,1,1,1,0], [1,1,0,1,0], [1,1,0,0,0], [0,0,0,0,0] ] 输出1示例 2输入grid [ [1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1] ] 输出3图解解题思路DFS 染色本解遍历网格每遇到1就发起一次 DFS将该岛屿的所有格子标记为2已访问同时岛屿计数 1。DFS 的边界条件越界、非1时返回。通过标记2避免重复访问。举例示例 2(0,0) 是 1 → DFS 标记 (0,0),(0,1),(1,0),(1,1) 为 2ans1 (2,2) 是 1 → DFS 标记 (2,2)ans2 (3,3) 是 1 → DFS 标记 (3,3),(3,4)ans3 最终3 ✅代码亮点使用 C23 的this auto dfs语法实现 lambda 递归写法简洁。复杂度时间 O(m×n)空间 O(m×n)递归栈C 代码classSolution{public:intnumIslands(vectorvectorchargrid){introwSizegrid.size();intcolSizegrid[0].size();intans0;autodfs[](thisautodfs,introw,intcol)-void{if(row0||rowrowSize||col0||colcolSize||grid[row][col]!1)return;grid[row][col]2;dfs(row,col-1);dfs(row,col1);dfs(row1,col);dfs(row-1,col);};for(inti0;irowSize;i){for(intj0;jcolSize;j){if(grid[i][j]1){dfs(i,j);ans;}}}returnans;}};二、994. Rotting Oranges腐烂的橘子 中等题目描述在给定的m × n网格grid中每个单元格可以有以下三个值之一0代表空单元格1代表新鲜橘子2代表腐烂的橘子每分钟腐烂的橘子周围 4 个方向上相邻的新鲜橘子都会腐烂。返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能返回-1。示例 1输入grid [[2,1,1],[1,1,0],[0,1,1]] 输出4示例 2输入grid [[2,1,1],[0,1,1],[1,0,1]] 输出-1左下角的 1 无法被感染示例 3输入grid [[0,2]] 输出0没有新鲜橘子图解解题思路多源 BFS本解同时从所有腐烂橘子出发做 BFS每一轮 BFS 相当于过一分钟。初始化统计所有新鲜橘子数量fresh将所有腐烂橘子位置加入队列BFS 过程每轮弹出当前队列中的所有腐烂橘子扩散到相邻新鲜橘子将其标记为2并加入队列fresh--轮次ans。终止当fresh 0或队列为空时停止。若结束后fresh 0说明有橘子无法腐烂返回-1。举例示例 1初始fresh6queue{(0,0)} 第1轮(0,0)扩散→(0,1),(1,0)腐烂fresh4ans1 第2轮(0,1),(1,0)扩散→(0,2),(1,1)腐烂fresh2ans2 第3轮(0,2),(1,1)扩散→(2,1)腐烂fresh1ans3 第4轮(2,1)扩散→(2,2)腐烂fresh0ans4 fresh0返回 4 ✅复杂度时间 O(m×n)空间 O(m×n)C 代码classSolution{public:intorangesRotting(vectorvectorintgrid){intans0;introwSizegrid.size();intcolSizegrid[0].size();queuepairint,intq;intfresh0;for(inti0;irowSize;i){for(intj0;jcolSize;j){if(grid[i][j]1)fresh;elseif(grid[i][j]2)q.push(make_pair(i,j));}}vectorvectorintdir{{1,0},{-1,0},{0,-1},{0,1}};while(fresh!q.empty()){intsizeq.size();for(intj0;jsize;j){autoposq.front();q.pop();for(inti0;idir.size();i){intxpos.firstdir[i][0];intypos.seconddir[i][1];if(x0xrowSizey0ycolSizegrid[x][y]1){fresh--;grid[x][y]2;q.push(make_pair(x,y));}}}ans;}returnfresh?-1:ans;}};三、207. Course Schedule课程表 中等题目描述你这个学期必须选修numCourses门课程记为0到numCourses - 1。在选修某些课程之前需要一些先修课程。先修课程按数组prerequisites给出其中prerequisites[i] [ai, bi]表示如果要学习课程ai则必须先学习课程bi。请你判断是否可能完成所有课程的学习示例 1输入numCourses 2, prerequisites [[1,0]] 输出true先上0再上1示例 2输入numCourses 2, prerequisites [[1,0],[0,1]] 输出false循环依赖图解解题思路拓扑排序BFS Kahn 算法本解如果课程间存在循环依赖则无法完成所有课程等价于判断有向图是否存在环。用拓扑排序BFS 版本建图umap[a]存 a 的前驱inDegree[b]b 有入度将所有入度为 0 的节点入队计数countBFS每次出队一个节点将其所有前驱的入度 -1若入度变为 0 则入队count若count numCourses说明所有节点都被处理过无环注意代码中umap[prerequisites[i][0]].push_back(prerequisites[i][1])即a → b方向a 依赖 bb 是 a 的先修inDegree[b]计的是 b 被依赖的次数b 被解锁后才能减少依赖 b 的课程的入度。举例[[1,0],[0,1]]循环inDegree [1, 1]0和1互相依赖 没有入度为0的节点count0 ≠ 2 返回 false ✅复杂度时间 O(VE)空间 O(VE)C 代码classSolution{public:boolcanFinish(intnumCourses,vectorvectorintprerequisites){unordered_mapint,vectorintumap;vectorintinDegre(numCourses,0);intcount0;queueintq;for(inti0;iprerequisites.size();i){umap[prerequisites[i][0]].push_back(prerequisites[i][1]);inDegre[prerequisites[i][1]];}for(inti0;inumCourses;i){if(!inDegre[i]){q.push(i);count;}}while(!q.empty()){intcoursesq.front();q.pop();vectorintcoursumap[courses];for(autocour:cours){inDegre[cour]--;if(!inDegre[cour]){q.push(cour);count;}}}return(countnumCourses);}};四、208. Implement Trie (Prefix Tree)实现 Trie 前缀树 中等题目描述Trie发音类似 “try”或者说前缀树是一种树形数据结构用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景例如自动补全和拼写检查。请你实现 Trie 类Trie()初始化前缀树对象void insert(String word)向前缀树中插入字符串wordboolean search(String word)如果word在前缀树中返回trueboolean startsWith(String prefix)如果之前已插入的字符串中有以prefix为前缀的字符串返回true示例输入 [Trie, insert, search, search, startsWith, insert, search] [[], [apple], [apple], [app], [app], [app], [app]] 输出[null, null, true, false, true, null, true]图解解题思路哈希表 Trie 节点本解每个节点TreeNode包含unordered_mapchar, TreeNode* umap子节点映射bool isEnd标记是否为某个单词的结尾三个操作insert从 root 出发对每个字符若不存在则新建节点最后标记isEnd truesearch从 root 出发沿字符遍历若中途找不到字符返回 false走完后返回cur-isEndstartsWith与 search 相同但最后直接返回 true不需要 isEnd举例insert “apple” 后 search “app”insert apple: root→a→p→p→l→e(isEndtrue) search app: root→a→p→p → cur 存在 走完了cur-isEnd falsep 不是单词结尾 返回 false ✅ startsWith app: root→a→p→p → 走完返回 true ✅复杂度时间 O(L)L 为字符串长度空间 O(总字符数)C 代码classTrie{structTreeNode{unordered_mapchar,TreeNode*umap;boolisEnd;TreeNode(){umap.clear();isEndfalse;}};public:TreeNode*root;Trie(){rootnewTreeNode();}voidinsert(string word){TreeNode*curroot;for(autoc:word){if(!cur-umap.count(c)){cur-umap[c]newTreeNode();}curcur-umap[c];}cur-isEndtrue;}boolsearch(string word){TreeNode*curroot;for(autoc:word){if(!cur-umap.count(c))returnfalse;curcur-umap[c];}returncur-isEnd;}boolstartsWith(string prefix){TreeNode*curroot;for(autoc:prefix){if(!cur-umap.count(c))returnfalse;curcur-umap[c];}returntrue;}};/** * Your Trie object will be instantiated and called as such: * Trie* obj new Trie(); * obj-insert(word); * bool param_2 obj-search(word); * bool param_3 obj-startsWith(prefix); */总结题号题目难度核心思路时间复杂度空间复杂度200岛屿数量 中等DFS 染色标记 ‘2’O(m×n)O(m×n)994腐烂的橘子 中等多源 BFS逐轮扩散O(m×n)O(m×n)207课程表 中等拓扑排序Kahn BFS判断有无环O(VE)O(VE)208实现 Trie 中等哈希表 Trie 节点isEnd 标记词尾O(L)O(总字符)如果这篇文章对你有帮助欢迎点赞收藏 ⭐也欢迎在评论区交流