LeetCode 959 Regions Cut By Slashes 题解：Go 并查集把斜杠网格切成连通区域

LeetCode 959 Regions Cut By Slashes 题解Go 并查集把斜杠网格切成连通区域【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文以 LeetCode-Go 仓库中 leetcode/0959.Regions-Cut-By-Slashes/README.md 为核心文档结合仓库内的完整 Go 源码与单元测试系统讲解 LeetCode 959「Regions Cut By Slashes」由斜杠划分区域的并查集解法。读完本文你将掌握「把每个 1x1 方格拆成 4 个小块、再用并查集合并连通块、最终统计连通块数量」这一经典建模思路并能直接复用仓库的并查集模板写出可运行、可通过全部官方示例的 Go 代码。一、题目回顾1.1 题意在一个由1 x 1小方格组成的N x N网格grid中每个小方格内要么是/、要么是\、要么是空白字符 。这些斜杠字符会把所在方格划分成若干个共边edge-adjacent的连续区域题目要求返回整个网格最终被划分成的区域总数。需要特别注意的是反斜杠的转义问题Go 字符串中\必须写成\\才能表示一个字符\。1.2 官方示例文档给出了 5 个官方示例仓库的单元测试文件 959. Regions Cut By Slashes_test.go 对这 5 个用例做了完整覆盖用例输入 grid输出区域数Example 1[ /, / ]2Example 2[ /, ]1Example 3[\\/, /\\]即\/与/\4Example 4[/\\, \\/]即/\与\/5Example 5[//, / ]31.3 数据约束1 grid.length grid[0].length 30网格是正方形边长最大 30grid[i][j]只能是/、\或 三者之一。由于输入规模很小最多 900 个格子并查集的代价几乎可以忽略这也使得本题非常适合作为并查集的入门与建模练习。二、核心建模把 1x1 方格拆成 4 个小块直接对原始方格做连通性分析是困难的因为一条斜线会把一个方格切成两个不规则的区域且斜线方向不同/与\切法还不对称。文档给出的解题思路非常巧妙先把每个 1x1 方格预先切成 4 个规整的小块再用并查集按斜线规则去合并它们。2.1 四分块与方向编号把每个小方格按「上下左右」切成 4 块并编号为编号 k位置0上方块1右方块2下方块3左方块那么整个N x N网格一共就有4 * N * N个小块每个小块都是并查集中的一个节点。任意两个小块之间只要没有被斜线隔开、或者跨越格子边界时边界两侧共边就把它们Union到同一个集合中。最终集合连通分量的个数就是区域数。2.2 斜线切分与 Union 规则遇到\从左上往右下切上方块与右方块同侧下方块与左方块同侧因此Union(0, 1)与Union(2, 3)遇到/从右上往左下切上方块与左方块同侧下方块与右方块同侧因此Union(0, 3)与Union(2, 1)遇到 空白整格连通4 块全部连通依次Union(0,1)、Union(2,1)、Union(2,3)最终 4 块合并为 1 个集合。2.3 跨格子的合并斜线只能切开同一个方格内部无法隔断相邻方格之间的公共边因此还需要把相邻格子之间的边界补齐上下相邻本行格子的下方块编号 2与下一行格子的上方块编号 0共边需要Union左右相邻本列格子的右方块编号 1与右边一列格子的左方块编号 3共边需要Union。以上规则在文档中均有明确描述并与仓库源码实现一一对应。三、并查集模板路径压缩 按秩合并解法复用了仓库template包中的通用并查集实现文件位于 template/UnionFind.go。type UnionFind struct { parent, rank []int count int } func (uf *UnionFind) Init(n int) { uf.count n uf.parent make([]int, n) uf.rank make([]int, n) for i : range uf.parent { uf.parent[i] i } } func (uf *UnionFind) Find(p int) int { root : p for root ! uf.parent[root] { root uf.parent[root] } // compress path for p ! uf.parent[p] { tmp : uf.parent[p] uf.parent[p] root p tmp } return root } func (uf *UnionFind) Union(p, q int) { proot : uf.Find(p) qroot : uf.Find(q) if proot qroot { return } if uf.rank[qroot] uf.rank[proot] { uf.parent[proot] qroot } else { uf.parent[qroot] proot if uf.rank[proot] uf.rank[qroot] { uf.rank[proot] } } uf.count-- }该模板的关键设计parent[i]记录节点i的父节点Init时每个节点自成一集count记录当前集合总数Find采用两趟遍历式路径压缩先向上找到根再沿原路径把所有节点直接挂到根上摊还复杂度接近常数Union采用按秩合并让秩较小的树挂到秩较大的树下当两棵树秩相等时秩加一从而把树高控制在O(log n)以内每次成功合并count--因此count天然就是连通分量的个数。本题最终答案可以直接通过统计根节点数量得到也可以利用模板的count语义理解。正是因为这个模板同时具备路径压缩与按秩合并本题在N 30的规模下单次操作的摊还复杂度可视为常数级。四、完整 Go 解法逐行讲解主解法位于 959. Regions Cut By Slashes.gofunc regionsBySlashes(grid []string) int { size : len(grid) uf : template.UnionFind{} uf.Init(4 * size * size) for i : 0; i size; i { for j : 0; j size; j { switch grid[i][j] { case \\: uf.Union(getFaceIdx(size, i, j, 0), getFaceIdx(size, i, j, 1)) uf.Union(getFaceIdx(size, i, j, 2), getFaceIdx(size, i, j, 3)) case /: uf.Union(getFaceIdx(size, i, j, 0), getFaceIdx(size, i, j, 3)) uf.Union(getFaceIdx(size, i, j, 2), getFaceIdx(size, i, j, 1)) case : uf.Union(getFaceIdx(size, i, j, 0), getFaceIdx(size, i, j, 1)) uf.Union(getFaceIdx(size, i, j, 2), getFaceIdx(size, i, j, 1)) uf.Union(getFaceIdx(size, i, j, 2), getFaceIdx(size, i, j, 3)) } if i size-1 { uf.Union(getFaceIdx(size, i, j, 2), getFaceIdx(size, i1, j, 0)) } if j size-1 { uf.Union(getFaceIdx(size, i, j, 1), getFaceIdx(size, i, j1, 3)) } } } count : 0 for i : 0; i 4*size*size; i { if uf.Find(i) i { count } } return count } func getFaceIdx(size, i, j, k int) int { return 4*(i*sizej) k }4.1 编号函数getFaceIdxfunc getFaceIdx(size, i, j, k int) int { return 4*(i*sizej) k }(i, j)定位格子k定位格内 4 块之一。全局编号4*(i*sizej)k保证每个小块都有唯一 ID且整个网格的编号区间正好是[0, 4*size*size)与uf.Init(4*size*size)严格对应。4.2 主流程三段式初始化uf.Init(4 * size * size)共4*N*N个节点初始每个小块自成一个集合按规则合并双层循环遍历每个格子switch分三种字符执行格内合并随后处理跨格边界——i size-1时把本格下方块与下一格上方块合并j size-1时把本格右方块与右一格左方块合并统计根节点Find(i) i即该节点是自己所在集合的根根的数量就是连通分量数量也就是题目所求的区域数。需要特别留意的细节Go 源码里反斜杠字符写作case \\这与文档强调的「反斜杠字符是转义的\用\\表示」完全一致而grid[i][j]取出的是单个字符与/、\\、 做比较即可。五、单元测试与官方示例验证测试文件 959. Regions Cut By Slashes_test.go 采用仓库惯用的para / ans结构组织用例5 个官方示例全部覆盖qs : []question959{ { para959{[]string{ /, / }}, ans959{2}, }, { para959{[]string{ /, }}, ans959{1}, }, { para959{[]string{\\/, /\\}}, ans959{4}, }, { para959{[]string{/\\, \\/}}, ans959{5}, }, { para959{[]string{//, / }}, ans959{3}, }, }测试逻辑非常直白遍历所有用例调用regionsBySlashes(p.one)并打印输入与输出人工比对预期答案即可验证实现正确性。从结构看仓库的测试组织方式把「参数」与「期望答案」分离para959/ans959便于后续追加用例。六、复杂度分析时间复杂度共有N*N个格子每个格子执行常数次Union最多 5 次并查集在路径压缩 按秩合并下摊还接近常数总复杂度约为O(N² · α(N²))其中α为反阿克曼函数空间复杂度parent与rank数组长度均为4*N*N即O(N²)。在题目约束N 30下节点总数最多 3600任何用例都能瞬间完成。七、总结LeetCode 959 的价值在于「建模」而非「算法本身」拆解斜线切出的不规则区域难以直接处理于是先人为把每个方格切成 4 个规整小块合并按\、/、空格三种情况定义格内合并规则再补齐上下、左右相邻格子的跨格合并计数并查集中根节点Find(i) i的个数就是最终区域数。从源码结构看仓库把并查集抽象为 template/UnionFind.go 通用模板路径压缩 按秩合并本题只需约 30 行业务代码即可完成建模与求解体现了「通用数据结构模板 题目专属建模」的组合套路。这种「把单元格细分再按规则合并」的思路同样适用于网格连通性、岛屿计数、区域划分等一大批 LeetCode 题目值得反复揣摩。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考