LeetCode热题100六236. 二叉树的最近公共祖先题目详情https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”示例 1[外链图片转存中…(img-bYSaKP6e-1773846495775)]输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1 输出3 解释节点 5 和节点 1 的最近公共祖先是节点 3 。示例 2输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4 输出5 解释节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。示例 3输入root [1,2], p 1, q 2 输出1解题过程想了很久没想出来看了解题思路才写出来核心思路是给定节点均在二叉树中则分左右遍历如果等于p/q则返回当左右均不等于null则认为该节点就是公共父节点如果有一侧即不为null也不等于p/q则继续往下寻找publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){if(rootnull||rootp||rootq){returnroot;}TreeNodeleftlowestCommonAncestor(root.left,p,q);TreeNoderightlowestCommonAncestor(root.right,p,q);if(left!nullright!null){returnroot;}returnleft!null?left:right;}200. 岛屿数量题目详情https://leetcode.cn/problems/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解题过程没有自己写出来核心原理是淹没碰到陆地将其置为0同时上下左右寻找1publicintnumIslands(char[][]grid){intcount0;if(gridnull||grid.length0){return0;}introwgrid.length;intcolumngrid[0].length;for(inti0;irow;i){for(intj0;jcolumn;j){if(grid[i][j]1){count;dfs(grid,i,j);}}}returncount;}publicvoiddfs(char[][]grid,inti,intj){introwgrid.length;intcolumngrid[0].length;if(i0||j0||irow||jcolumn||grid[i][j]0){return;}grid[i][j]0;dfs(grid,i-1,j);dfs(grid,i1,j);dfs(grid,i,j-1);dfs(grid,i,j1);}994. 腐烂的橘子题目详情https://leetcode.cn/problems/rotting-oranges/在给定的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 。解答过程用了一个很笨的方法写出来的扫一遍表格记录下来橘子循环遍历坏橘子直至好橘子个数为0或者不变publicintorangesRotting(int[][]grid){if(gridnull||grid.length0){return-1;}HashSetIntegerhashSet1newHashSet();HashSetIntegerhashSet2newHashSet();intminute0;introwgrid.length;intcolumngrid[0].length;for(inti0;irow;i){for(intj0;jcolumn;j){if(grid[i][j]1){hashSet1.add((i1)*100(j1));}elseif(grid[i][j]2){hashSet2.add((i1)*100(j1));}}}if(hashSet1.isEmpty()){return0;}intsizehashSet1.size();HashSetIntegerhashSet3;while(!hashSet1.isEmpty()){minute;hashSet3newHashSet();for(Integerinteger:hashSet2){intiinteger/100;intjinteger%100;intright1(i1)*100j;if(hashSet1.contains(right1)){hashSet3.add(right1);hashSet1.remove(right1);}intleft1(i-1)*100j;if(hashSet1.contains(left1)){hashSet3.add(left1);hashSet1.remove(left1);}intbottom1i*100j1;if(hashSet1.contains(bottom1)){hashSet3.add(bottom1);hashSet1.remove(bottom1);}inttop1i*100j-1;if(hashSet1.contains(top1)){hashSet3.add(top1);hashSet1.remove(top1);}}if(sizehashSet1.size()){return-1;}else{sizehashSet1.size();}hashSet2hashSet3;}returnminute;}看了解答过程回避自己写出来的更好一点核心是利用minute 3每次判断只对受影响的橘子进行判断publicintorangesRotting(int[][]grid){if(gridnull||grid.length0){return-1;}intorange0;for(inti0;igrid.length;i){for(intj0;jgrid[i].length;j){if(grid[i][j]1){orange;}}}if(orange0){return0;}intminute0;intinfection_orange;while(true){for(int[]ints:grid){System.out.println(Arrays.toString(ints));}infection_orange0;for(inti0;igrid.length;i){for(intj0;jgrid[i].length;j){if(grid[i][j]2minute){if(i-10grid[i-1][j]1){infection_orange;grid[i-1][j]minute3;}if(i1grid.lengthgrid[i1][j]1){infection_orange;grid[i1][j]minute3;}if(j-10grid[i][j-1]1){infection_orange;grid[i][j-1]minute3;}if(j1grid[i].lengthgrid[i][j1]1){infection_orange;grid[i][j1]minute3;}}}}minute;if(infection_orange0){return-1;}else{orange-infection_orange;if(orange0){break;}}}returnminute;}207. 课程表题目详情https://leetcode.cn/problems/course-schedule/你这个学期必须选修numCourses门课程记为0到numCourses - 1。在选修某些课程之前需要一些先修课程。 先修课程按数组prerequisites给出其中prerequisites[i] [ai, bi]表示如果要学习课程ai则必须先学习课程bi。例如先修课程对[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 。这是不可能的。提示1 numCourses 20000 prerequisites.length 5000prerequisites[i].length 20 ai, bi numCoursesprerequisites[i]中的所有课程对互不相同解答过程ArrayListListIntegeredges;int[]visited;booleanvalidtrue;publicbooleancanFinish(intnumCourses,int[][]prerequisites){edgesnewArrayList();for(inti0;inumCourses;i){edges.add(newArrayList());}for(int[]prerequisite:prerequisites){edges.get(prerequisite[0]).add(prerequisite[1]);}// System.out.println(edges);intindex0;visitednewint[numCourses];while(numCourses0){System.out.println(numCourses: numCourses);if(visited[index]0){dfs(index);}// System.out.println(Arrays.toString(visited));index;numCourses--;}returnvalid;}publicvoiddfs(intindex){visited[index]1;ListIntegercoursesedges.get(index);// System.out.println(index: index);// System.out.println(courses: courses);for(Integercours:courses){if(!valid){return;}if(visited[cours]0){dfs(cours);}elseif(visited[cours]1){validfalse;return;}}visited[index]2;}208. 实现 Trie (前缀树)题目详情https://leetcode.cn/problems/implement-trie-prefix-tree/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); // 返回 True trie.search(app); // 返回 False trie.startsWith(app); // 返回 True trie.insert(app); trie.search(app); // 返回 True解答过程看到题目就直接用arraylist了。。。解答过程异常顺利还有点疑惑为什么这题会是中等看答案到明白原来是考察树classTrie{ArrayListStringarrayList;publicTrie(){arrayListnewArrayList();}publicvoidinsert(Stringword){arrayList.add(word);}publicbooleansearch(Stringword){returnarrayList.contains(word);}publicbooleanstartsWith(Stringprefix){for(Stringstr:arrayList){if(str.startsWith(prefix)){returntrue;}}returnfalse;}}核心思路是将字符串拆分为字符拼接成树用于快速检索字符串/字符串前缀是否在树中classTrie{privatefinalTrie[]children;booleanend;publicTrie(){this.childrennewTrie[26];this.endfalse;}publicvoidinsert(Stringword){Trienodethis;for(charc:word.toCharArray()){intindexc-a;if(node.children[index]null){node.children[index]newTrie();}nodenode.children[index];}node.endtrue;}publicbooleansearch(Stringword){TrienodesearchPrefix(word);returnnode!nullnode.end;}publicbooleanstartsWith(Stringprefix){returnsearchPrefix(prefix)!null;}publicTriesearchPrefix(Stringprefix){Trienodethis;for(charc:prefix.toCharArray()){intindexc-a;if(node.children[index]null){returnnull;}nodenode.children[index];}returnnode;}}
LeetCode热题100（六）
发布时间：2026/5/19 19:46:27
LeetCode热题100六236. 二叉树的最近公共祖先题目详情https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”示例 1[外链图片转存中…(img-bYSaKP6e-1773846495775)]输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1 输出3 解释节点 5 和节点 1 的最近公共祖先是节点 3 。示例 2输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4 输出5 解释节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。示例 3输入root [1,2], p 1, q 2 输出1解题过程想了很久没想出来看了解题思路才写出来核心思路是给定节点均在二叉树中则分左右遍历如果等于p/q则返回当左右均不等于null则认为该节点就是公共父节点如果有一侧即不为null也不等于p/q则继续往下寻找publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){if(rootnull||rootp||rootq){returnroot;}TreeNodeleftlowestCommonAncestor(root.left,p,q);TreeNoderightlowestCommonAncestor(root.right,p,q);if(left!nullright!null){returnroot;}returnleft!null?left:right;}200. 岛屿数量题目详情https://leetcode.cn/problems/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解题过程没有自己写出来核心原理是淹没碰到陆地将其置为0同时上下左右寻找1publicintnumIslands(char[][]grid){intcount0;if(gridnull||grid.length0){return0;}introwgrid.length;intcolumngrid[0].length;for(inti0;irow;i){for(intj0;jcolumn;j){if(grid[i][j]1){count;dfs(grid,i,j);}}}returncount;}publicvoiddfs(char[][]grid,inti,intj){introwgrid.length;intcolumngrid[0].length;if(i0||j0||irow||jcolumn||grid[i][j]0){return;}grid[i][j]0;dfs(grid,i-1,j);dfs(grid,i1,j);dfs(grid,i,j-1);dfs(grid,i,j1);}994. 腐烂的橘子题目详情https://leetcode.cn/problems/rotting-oranges/在给定的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 。解答过程用了一个很笨的方法写出来的扫一遍表格记录下来橘子循环遍历坏橘子直至好橘子个数为0或者不变publicintorangesRotting(int[][]grid){if(gridnull||grid.length0){return-1;}HashSetIntegerhashSet1newHashSet();HashSetIntegerhashSet2newHashSet();intminute0;introwgrid.length;intcolumngrid[0].length;for(inti0;irow;i){for(intj0;jcolumn;j){if(grid[i][j]1){hashSet1.add((i1)*100(j1));}elseif(grid[i][j]2){hashSet2.add((i1)*100(j1));}}}if(hashSet1.isEmpty()){return0;}intsizehashSet1.size();HashSetIntegerhashSet3;while(!hashSet1.isEmpty()){minute;hashSet3newHashSet();for(Integerinteger:hashSet2){intiinteger/100;intjinteger%100;intright1(i1)*100j;if(hashSet1.contains(right1)){hashSet3.add(right1);hashSet1.remove(right1);}intleft1(i-1)*100j;if(hashSet1.contains(left1)){hashSet3.add(left1);hashSet1.remove(left1);}intbottom1i*100j1;if(hashSet1.contains(bottom1)){hashSet3.add(bottom1);hashSet1.remove(bottom1);}inttop1i*100j-1;if(hashSet1.contains(top1)){hashSet3.add(top1);hashSet1.remove(top1);}}if(sizehashSet1.size()){return-1;}else{sizehashSet1.size();}hashSet2hashSet3;}returnminute;}看了解答过程回避自己写出来的更好一点核心是利用minute 3每次判断只对受影响的橘子进行判断publicintorangesRotting(int[][]grid){if(gridnull||grid.length0){return-1;}intorange0;for(inti0;igrid.length;i){for(intj0;jgrid[i].length;j){if(grid[i][j]1){orange;}}}if(orange0){return0;}intminute0;intinfection_orange;while(true){for(int[]ints:grid){System.out.println(Arrays.toString(ints));}infection_orange0;for(inti0;igrid.length;i){for(intj0;jgrid[i].length;j){if(grid[i][j]2minute){if(i-10grid[i-1][j]1){infection_orange;grid[i-1][j]minute3;}if(i1grid.lengthgrid[i1][j]1){infection_orange;grid[i1][j]minute3;}if(j-10grid[i][j-1]1){infection_orange;grid[i][j-1]minute3;}if(j1grid[i].lengthgrid[i][j1]1){infection_orange;grid[i][j1]minute3;}}}}minute;if(infection_orange0){return-1;}else{orange-infection_orange;if(orange0){break;}}}returnminute;}207. 课程表题目详情https://leetcode.cn/problems/course-schedule/你这个学期必须选修numCourses门课程记为0到numCourses - 1。在选修某些课程之前需要一些先修课程。 先修课程按数组prerequisites给出其中prerequisites[i] [ai, bi]表示如果要学习课程ai则必须先学习课程bi。例如先修课程对[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 。这是不可能的。提示1 numCourses 20000 prerequisites.length 5000prerequisites[i].length 20 ai, bi numCoursesprerequisites[i]中的所有课程对互不相同解答过程ArrayListListIntegeredges;int[]visited;booleanvalidtrue;publicbooleancanFinish(intnumCourses,int[][]prerequisites){edgesnewArrayList();for(inti0;inumCourses;i){edges.add(newArrayList());}for(int[]prerequisite:prerequisites){edges.get(prerequisite[0]).add(prerequisite[1]);}// System.out.println(edges);intindex0;visitednewint[numCourses];while(numCourses0){System.out.println(numCourses: numCourses);if(visited[index]0){dfs(index);}// System.out.println(Arrays.toString(visited));index;numCourses--;}returnvalid;}publicvoiddfs(intindex){visited[index]1;ListIntegercoursesedges.get(index);// System.out.println(index: index);// System.out.println(courses: courses);for(Integercours:courses){if(!valid){return;}if(visited[cours]0){dfs(cours);}elseif(visited[cours]1){validfalse;return;}}visited[index]2;}208. 实现 Trie (前缀树)题目详情https://leetcode.cn/problems/implement-trie-prefix-tree/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); // 返回 True trie.search(app); // 返回 False trie.startsWith(app); // 返回 True trie.insert(app); trie.search(app); // 返回 True解答过程看到题目就直接用arraylist了。。。解答过程异常顺利还有点疑惑为什么这题会是中等看答案到明白原来是考察树classTrie{ArrayListStringarrayList;publicTrie(){arrayListnewArrayList();}publicvoidinsert(Stringword){arrayList.add(word);}publicbooleansearch(Stringword){returnarrayList.contains(word);}publicbooleanstartsWith(Stringprefix){for(Stringstr:arrayList){if(str.startsWith(prefix)){returntrue;}}returnfalse;}}核心思路是将字符串拆分为字符拼接成树用于快速检索字符串/字符串前缀是否在树中classTrie{privatefinalTrie[]children;booleanend;publicTrie(){this.childrennewTrie[26];this.endfalse;}publicvoidinsert(Stringword){Trienodethis;for(charc:word.toCharArray()){intindexc-a;if(node.children[index]null){node.children[index]newTrie();}nodenode.children[index];}node.endtrue;}publicbooleansearch(Stringword){TrienodesearchPrefix(word);returnnode!nullnode.end;}publicbooleanstartsWith(Stringprefix){returnsearchPrefix(prefix)!null;}publicTriesearchPrefix(Stringprefix){Trienodethis;for(charc:prefix.toCharArray()){intindexc-a;if(node.children[index]null){returnnull;}nodenode.children[index];}returnnode;}}
