力扣Hot100系列22（Java）——[图论]总结(岛屿数量，腐烂的橘子，课程表，实现Trie（前缀树）)

文章目录前言一、岛屿数量1.题目2.代码3.例子二、腐烂的橘子1.题目2.代码3.例子输入网格三、课程表1.题目2.代码3.例子例 1无环 → 可以修完课返回 true例 2有环 → 不能修完课返回 false四、实现Trie前缀树1.题目2.代码3.例子前言本文记录力扣Hot100里面关于图论的四道题包括常见解法和一些关键步骤理解也有例子便于大家理解一、岛屿数量1.题目给你一个由 ‘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’]]输出32.代码classSolution{// DFS 函数从 (r,c) 开始把整片相连的陆地全部变成 0voiddfs(char[][]grid,intr,intc){intnrgrid.length;// 网格一共有多少行intncgrid[0].length;// 网格一共有多少列// 如果越界 或者 当前是水直接返回if(r0||c0||rnr||cnc||grid[r][c]0){return;}grid[r][c]0;// 把当前陆地淹没标记为已访问dfs(grid,r-1,c);// 往上搜索dfs(grid,r1,c);// 往下搜索dfs(grid,r,c-1);// 往左搜索dfs(grid,r,c1);// 往右搜索}// 主函数计算岛屿数量publicintnumIslands(char[][]grid){// 如果网格为空直接返回 0if(gridnull||grid.length0){return0;}intnrgrid.length;// 行数intncgrid[0].length;// 列数intnum_islands0;// 岛屿数量初始 0// 遍历整个网格的每一个格子for(intr0;rnr;r){for(intc0;cnc;c){// 发现一块没被访问过的陆地if(grid[r][c]1){num_islands;// 岛屿数量 1dfs(grid,r,c);// DFS 淹没整个岛屿}}}returnnum_islands;// 返回最终岛屿总数}}3.例子[1,1,0,0,0] [1,1,0,0,0] [0,0,1,0,0] [0,0,0,1,1]第一步初始化行数nr 4列数nc 5岛屿数量num_islands 0开始双重循环遍历每一格第 1 个格子(0,0) →值是 ‘1’num_islands从 0 → 1调用dfs(0,0)DFS 开始淹没整片相连的 1DFS 淹没过程自动把相连 1 全变 0(0,0) → 变 0(0,1) → 变 0(1,0) → 变 0(1,1) → 变 0淹没后网格变成[0,0,0,0,0] [0,0,0,0,0] [0,0,1,0,0] [0,0,0,1,1]继续遍历(0,2)0、(0,3)0、(0,4)0(1,0)0、(1,1)0、(1,2)0、(1,3)0、(1,4)0走到 (2,2) →值是 ‘1’num_islands从 1 → 2调用dfs(2,2)淹没这个单独的 1 → 变 0网格现在[0,0,0,0,0] [0,0,0,0,0] [0,0,0,0,0] [0,0,0,1,1]继续遍历(2,3)0、(2,4)0(3,0)0、(3,1)0、(3,2)0走到 (3,3) →值是 ‘1’num_islands从 2 → 3调用dfs(3,3)淹没(3,3) → 0(3,4) → 0最终网格全是 0[0,0,0,0,0] [0,0,0,0,0] [0,0,0,0,0] [0,0,0,0,0]遍历结束返回num_islands 3二、腐烂的橘子1.题目在给定的 m x 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解释左下角的橘子第 2 行 第 0 列永远不会腐烂因为腐烂只会发生在 4 个方向上。示例 3输入grid [[0,2]]输出0解释因为 0 分钟时已经没有新鲜橘子了所以答案就是 0 。提示m grid.lengthn grid[i].length1 m, n 10grid[i][j] 仅为 0、1 或 22.代码classSolution{// 上下左右四个方向的坐标偏移量privatestaticfinalint[][]DIRECTIONS{{-1,0},{1,0},{0,-1},{0,1}};publicintorangesRotting(int[][]grid){intmgrid.length;// 网格行数intngrid[0].length;// 网格列数intfresh0;// 新鲜橘子数量Listint[]badListnewArrayList();// 存放当前腐烂的橘子// 第一步遍历网格统计初始数据for(inti0;im;i){for(intj0;jn;j){if(grid[i][j]1){fresh;// 遇到新鲜橘子计数1}elseif(grid[i][j]2){badList.add(newint[]{i,j});// 遇到腐烂橘子加入队列}}}intans0;// 记录总共需要的分钟数// 第二步BFS 扩散腐烂循环直到没有新鲜橘子 或 没有可扩散的腐烂橘子while(fresh0!badList.isEmpty()){ans;// 每轮循环 过去1分钟Listint[]tmpbadList;// 取出这一分钟要扩散的所有橘子badListnewArrayList();// 清空准备存下一分钟新腐烂的橘子// 遍历当前所有腐烂橘子让它们同时向四周扩散for(int[]pos:tmp){for(int[]dir:DIRECTIONS){// 遍历上下左右intipos[0]dir[0];intjpos[1]dir[1];// 判断坐标是否合法 是新鲜橘子if(0iim0jjngrid[i][j]1){fresh--;// 新鲜橘子变少grid[i][j]2;// 变成腐烂橘子badList.add(newint[]{i,j});// 加入下一轮扩散}}}}// 最后如果还有新鲜橘子剩下返回-1否则返回时间returnfresh0?-1:ans;}}3.例子我用你给的** exact 例子**一步一步、逐分钟带你走一遍代码让你彻底看懂输入网格grid [ [2, 1, 1], [1, 1, 0], [0, 1, 1] ]数字含义2 腐烂橘子1 新鲜橘子0 空第一步代码先遍历整个网格[2,1,1] [1,1,0] [0,1,1]代码统计结果fresh 6个新鲜橘子badList [ (0,0) ]1 个腐烂橘子ans 0第二步开始 BFS 扩散按分钟走第 1 分钟开始ans从 0 → 1当前要扩散的腐烂橘子(0,0)上下左右上越界下(1,0) 1 → 变 2左越界右(0,1) 1 → 变 2新腐烂橘子(1,0)、(0,1)fresh 6 - 2 4网格现在[2, 2, 1] [2, 1, 0] [0, 1, 1]第 2 分钟ans从 1 → 2当前扩散(0,1)、(1,0)(0,1) 扩散右 (0,2) 1 → 变 2(1,0) 扩散下 (2,0) 0 不变右 (1,1) 1 → 变 2新腐烂(0,2)、(1,1)fresh 4 - 2 2网格[2, 2, 2] [2, 2, 0] [0, 1, 1]第 3 分钟ans从 2 → 3当前扩散(0,2)、(1,1)(0,2) 扩散周围无新鲜橘子(1,1) 扩散下 (2,1) 1 → 变 2新腐烂(2,1)fresh 2 - 1 1网格[2, 2, 2] [2, 2, 0] [0, 2, 1]第 4 分钟ans从 3 → 4当前扩散(2,1)(2,1) 扩散右 (2,2) 1 → 变 2新腐烂(2,2)fresh 1 - 1 0网格[2, 2, 2] [2, 2, 0] [0, 2, 2]第三步结束循环fresh 0→ 没有新鲜橘子了返回ans 4三、课程表1.题目你这个学期必须选修 numCourses 门课程记为 0 到 numCourses - 1 。在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出其中prerequisites[i] [a(i), b(i)] 表示如果要学习课程 a(i) 则 必须 先学习课程 b(i)( )。例如先修课程对 [0, 1] 表示想要学习课程 0 你需要先完成课程 1 。请你判断是否可能完成所有课程的学习如果可以返回 true 否则返回 false 。示例 1输入numCourses 2, prerequisites [[1,0]]输出true解释总共有 2 门课程。学习课程 1 之前你需要完成课程 0 。这是可能的。示例 2输入numCourses 2, prerequisites [[1,0],[0,1]]输出false解释总共有 2 门课程。学习课程 1 之前你需要先完成课程 0 并且学习课程 0 之前你还应先完成课程 1 。这是不可能的。2.代码classSolution{// 全局变量存储图的邻接表课程依赖关系ListListIntegeredges;// 标记每个课程的访问状态0未访问 1访问中 2已访问完int[]visited;// 标记是否无环默认无环true发现环改成falsebooleanvalidtrue;// 主方法输入课程总数、课程依赖数组返回能否修完课publicbooleancanFinish(intnumCourses,int[][]prerequisites){// 初始化邻接表给每一门课程创建一个空的依赖列表edgesnewArrayListListInteger();for(inti0;inumCourses;i){edges.add(newArrayListInteger());}// 初始化状态数组所有课程默认未访问0visitednewint[numCourses];// 构建有向图[后修课, 先修课] → 存为 先修课 → 后修课 的边for(int[]info:prerequisites){edges.get(info[1]).add(info[0]);}// 遍历所有课程只要没发现环就对未访问的课程做DFSfor(inti0;inumCoursesvalid;i){if(visited[i]0){dfs(i);}}// 最终返回无环true有环falsereturnvalid;}// DFS核心深度遍历检测是否有环publicvoiddfs(intu){// 标记当前课程正在遍历中状态1visited[u]1;// 遍历当前课程的所有后续课程for(intv:edges.get(u)){if(visited[v]0){// 后续课程没访问过 → 继续DFSdfs(v);// 子递归发现环直接退出不用继续遍历if(!valid)return;}elseif(visited[v]1){// 遇到了【正在遍历中】的节点 → 找到环validfalse;return;}}// 当前课程所有后续都遍历完了 → 标记为已完成状态2visited[u]2;}}3.例子例 1无环 → 可以修完课返回 true输入numCourses 2 prerequisites [[1,0]]含义想学课程 1必须先学课程 0图0 → 1代码执行步骤1. 初始化edges [[], []]visited [0, 0]valid true2. 建图info [1,0]edges.get(0).add(1)→edges [ [1], [] ]3. 遍历课程i0visited[0]0 → 调用 dfs(0)** 执行 dfs(0)**visited[0] 1标记正在访问遍历邻居v1visited[1] 0→ 调用dfs(1)执行 dfs(1)visited[1] 1没有邻居visited[1] 2标记完成返回回到 dfs(0)循环结束visited[0] 2返回4. 结束valid true→返回 true例 2有环 → 不能修完课返回 false输入numCourses 2 prerequisites [[1,0], [0,1]]含义学 1 先学 0学 0 先学 1 →死循环环图0 ↔ 1代码执行步骤1. 建图edges.get(0).add(1)edges.get(1).add(0)→edges [ [1], [0] ]2. 开始 dfs(0)visited[0] 1遍历邻居v1visited[1]0→ dfs(1)执行 dfs(1)visited[1] 1遍历邻居v0visited[0] 1正在访问发现环valid falsereturn回到 dfs(0)发现validfalse→ return3. 结束valid false→返回 false四、实现Trie前缀树1.题目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”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”][[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]输出[null, null, true, false, true, null, true]解释Trie trie new Trie();trie.insert(“apple”);trie.search(“apple”); // 返回 Truetrie.search(“app”); // 返回 Falsetrie.startsWith(“app”); // 返回 Truetrie.insert(“app”);trie.search(“app”); // 返回 True提示1 word.length, prefix.length 2000word 和 prefix 仅由小写英文字母组成insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次2.代码classTrie{// 子节点数组每个节点最多有26个孩子对应小写字母a-zprivateTrie[]children;// 标记当前节点是否是一个单词的结尾privatebooleanisEnd;// 构造方法初始化字典树节点publicTrie(){childrennewTrie[26];// 26个字母所以数组长度26isEndfalse;// 默认不是单词结尾}// 插入一个单词到字典树publicvoidinsert(Stringword){Trienodethis;// 从根节点开始for(inti0;iword.length();i){// 遍历单词的每一个字符charchword.charAt(i);// 取出当前字符intindexch-a;// 转成数组下标 0~25if(node.children[index]null){// 如果该子节点不存在node.children[index]newTrie();// 新建节点}nodenode.children[index];// 移动到子节点继续处理下一个字符}node.isEndtrue;// 单词全部插入完成标记最后一个节点为单词结尾}// 查找单词是否存在必须完全匹配publicbooleansearch(Stringword){TrienodesearchPrefix(word);// 查找前缀returnnode!nullnode.isEnd;// 找到且是单词结尾才返回true}// 判断是否存在以 prefix 为前缀的单词publicbooleanstartsWith(Stringprefix){returnsearchPrefix(prefix)!null;// 只要能找到前缀就返回true}// 私有工具方法查找前缀返回最后一个节点privateTriesearchPrefix(Stringprefix){Trienodethis;// 从根节点开始for(inti0;iprefix.length();i){// 遍历前缀字符charchprefix.charAt(i);intindexch-a;if(node.children[index]null){// 某个字符不存在returnnull;// 前缀不存在返回null}nodenode.children[index];// 继续往下走}returnnode;// 遍历完成返回当前节点}}3.例子例操作序列 [Trie, insert, search, search, startsWith, insert, search] 参数 [[], [apple], [apple], [app], [app], [app], [app]] 输出 [null, null, true, false, true, null, true]第1步执行 Trie() —— 创建字典树操作新建一棵空字典树此时只有根节点没有任何字母没有任何单词输出null第2步执行 insert(“apple”) —— 插入单词 apple开始逐字符往下建路径从根节点出发字符a→ 没有新建节点字符p→ 没有新建节点字符p→ 没有新建节点字符l→ 没有新建节点字符e→ 没有新建节点到达最后一个字符e把它标记isEnd true表示到这里是一个完整单词现在树里的路径根 → a → p → p → l → e标记结束输出null第3步执行 search(“apple”) —— 查找完整单词 apple逐字符查找a存在p存在p存在l存在e存在最后一个节点e被标记为结束isEnd true→ 两个条件都满足路径存在 是单词结尾→ 结果true第4步执行 search(“app”) —— 查找完整单词 app逐字符查找a存在p存在p存在路径走完了但是最后这个p节点没有标记 isEnd true它只是 apple 中间的一个节点不是单词结尾。search要求必须是完整单词才返回 true→ 结果false第5步执行 startsWith(“app”) —— 判断是否有以 app 开头的单词startsWith规则只要路径能走完就返回 true不管是不是单词结尾。a存在p存在p存在路径完全能走通 → 结果true第6步执行 insert(“app”) —— 插入单词 app现在插入 app走到a → p → p把最后这个p节点标记 isEnd true现在树里有两个单词appp标记结束applee标记结束路径变成根 → a → p → p结束→ l → e结束输出null第7步执行 search(“app”) —— 再次查找完整单词 app现在路径a→p→p存在最后p节点已经被标记 isEnd true→ 满足完整单词条件→ 结果true最终输出结果[null, null, true, false, true, null, true]如果本篇文章对您有帮助可以点赞收藏或评论哦关注主包不迷路让我们一起向前进步吧