LeetCode 补拙笔记 日期：2026.05.29 题目：1559. 二维网格图中探测环

LeetCode 补拙笔记0. 前言日期2026.05.29题目1559. 二维网格图中探测环难度中等标签并查集、图论、DFS1. 题目理解问题描述给定一个二维字符网格grid判断网格中是否存在由相同字符构成的环。环的定义是一条长度 ≥ 4 的路径起点和终点为同一个格子路径中不能直接回到上一步所在的格子。示例输入grid [[a,a,a,a],[a,b,b,a],[a,b,b,a],[a,a,a,a]]输出true解释外层的a和内层的b都各自形成了环。2. 解题思路核心观察环的存在等价于在无向图中两个连通的节点被再次合并时会形成环。可以用并查集Union-Find解决遍历相邻格子若字符相同则尝试合并合并前发现两节点已连通说明存在环。算法步骤初始化并查集每个格子为独立集合。遍历网格对每个格子只检查右侧和下侧的邻居避免重复检查。若当前格子与邻居字符相同执行合并操作。合并时若发现两节点已连通说明形成了环直接返回true。遍历结束未发现环返回false。3. 代码实现packagelc1559;classSolution{publicbooleancontainsCycle(char[][]grid){intngrid.length;if(n0)returnfalse;intmgrid[0].length;int[]parentnewint[n*m];for(inti0;in*m;i){parent[i]i;}for(inti0;in;i){for(intj0;jm;j){charcgrid[i][j];// 向右看if(j1mgrid[i][j1]c){intui*mj;intvi*m(j1);if(union(parent,u,v)){returntrue;}}if(i1ngrid[i1][j]c){intui*mj;intv(i1)*mj;if(union(parent,u,v)){returntrue;}}}}returnfalse;}privateintfind(int[]parent,intx){introotx;while(parent[root]!root){rootparent[root];}while(parent[x]!root){intnextparent[x];parent[x]root;xnext;}returnroot;}privatebooleanunion(int[]parent,intx,inty){introotXfind(parent,x);introotYfind(parent,y);if(rootXrootY){returntrue;}parent[rootY]rootX;returnfalse;}}4. 代码优化说明代码未做任何修改仅添加注释讲解classSolution{publicbooleancontainsCycle(char[][]grid){intlen1grid.length;intlen2grid[0].length;// 并查集数组索引表示格子编号值为父节点int[]anewint[len1*len2];a[0]0;// 初始化第一行的父节点for(intj1;jlen2;j){// 若与左侧字符相同继承左侧的父节点否则父节点为自身if(grid[0][j]grid[0][j-1]){a[j]a[j-1];}else{a[j]j;}}intklen2;// 遍历后续每一行for(inti1;ilen1;i){// 初始化每行第一个格子的父节点if(grid[i][0]grid[i-1][0]){a[k]a[i*len2-len2];}else{a[k]k;}k;// 遍历每行后续的格子for(intj1;jlen2;j,k){// 先处理左侧邻居if(grid[i][j]grid[i][j-1]){a[k]a[k-1];}else{a[k]k;}// 再处理上方邻居判断是否形成环if(grid[i][j]grid[i-1][j]){// 若当前格子与上方格子已连通则存在环if(fn(a,k)fn(a,k-len2)){returntrue;}else{// 合并两个集合a[a[k-len2]]a[k];}}}}returnfalse;}// 路径压缩的查找函数publicintfn(int[]a,intk){if(a[k]!k){a[k]fn(a,a[k]);}returna[k];}}5. 复杂度分析时间复杂度O(n×m⋅α(n×m))O(n \times m \cdot \alpha(n \times m))O(n×m⋅α(n×m))其中nnn和mmm为网格的行列数α\alphaα为阿克曼函数的反函数近似为常数。并查集的查找和合并操作几乎是常数时间。空间复杂度O(n×m)O(n \times m)O(n×m)主要为并查集数组的开销。6. 总结核心思路并查集检测环通过合并相同字符的相邻节点利用连通性判断环的存在。优化后代码在遍历顺序和并查集初始化上做了简化逻辑更紧凑。关键技巧只检查右侧和下侧邻居避免重复合并路径压缩优化查找效率。