当前位置：首页 > news >正文

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

news 2026/6/3 23:09:44

LeetCode 补拙笔记

0. 前言

日期：2026.05.29
题目：1559. 二维网格图中探测环
难度：中等
标签：并查集、图论、DFS

1. 题目理解

问题描述：
给定一个二维字符网格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){intn=grid.length;if(n==0)returnfalse;intm=grid[0].length;int[]parent=newint[n*m];for(inti=0;i<n*m;i++){parent[i]=i;}for(inti=0;i<n;i++){for(intj=0;j<m;j++){charc=grid[i][j];// 向右看if(j+1<m&&grid[i][j+1]==c){intu=i*m+j;intv=i*m+(j+1);if(union(parent,u,v)){returntrue;}}if(i+1<n&&grid[i+1][j]==c){intu=i*m+j;intv=(i+1)*m+j;if(union(parent,u,v)){returntrue;}}}}returnfalse;}privateintfind(int[]parent,intx){introot=x;while(parent[root]!=root){root=parent[root];}while(parent[x]!=root){intnext=parent[x];parent[x]=root;x=next;}returnroot;}privatebooleanunion(int[]parent,intx,inty){introotX=find(parent,x);introotY=find(parent,y);if(rootX==rootY){returntrue;}parent[rootY]=rootX;returnfalse;}}

4. 代码优化说明

（代码未做任何修改，仅添加注释讲解）

classSolution{publicbooleancontainsCycle(char[][]grid){intlen1=grid.length;intlen2=grid[0].length;// 并查集数组，索引表示格子编号，值为父节点int[]a=newint[len1*len2];a[0]=0;// 初始化第一行的父节点for(intj=1;j<len2;j++){// 若与左侧字符相同，继承左侧的父节点；否则父节点为自身if(grid[0][j]==grid[0][j-1]){a[j]=a[j-1];}else{a[j]=j;}}intk=len2;// 遍历后续每一行for(inti=1;i<len1;i++){// 初始化每行第一个格子的父节点if(grid[i][0]==grid[i-1][0]){a[k]=a[i*len2-len2];}else{a[k]=k;}k++;// 遍历每行后续的格子for(intj=1;j<len2;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)
主要为并查集数组的开销。