标签搜索

目 录CONTENT

文章目录

【算法模板】并查集

陈铭
2022-12-18 / 0 评论 / 0 点赞 / 200 阅读 / 981 字 / 正在检测是否收录...

例题:由斜杠划分区域

力扣面试题 959题为例:

在由 1 x 1 方格组成的 n x n 网格 grid 中,每个 1 x 1 方块由 ‘/’、‘’ 或空格构成。这些字符会将方块划分为一些共边的区域。

给定网格 grid 表示为一个字符串数组,返回 区域的数量 。

请注意,反斜杠字符是转义的,因此 ‘’ 用 ‘\’ 表示。


示例 1:
image
输入:grid = [" /“,”/ "]
输出:2

示例 2:
image
输入:grid = [" /“,” "]
输出:1

示例 3:
image
输入:grid = [“/\”,“\/”]
输出:5
解释:回想一下,因为 \ 字符是转义的,所以 “/\” 表示 /\,而 “\/” 表示 /。


方法:并查集
「斜杠」、「反斜杠」把单元格拆分成的 2 个三角形的形态,在做合并的时候需要分类讨论。根据「斜杠」、「反斜杠」 分割的特点,我们把一个单元格分割成逻辑上的 4 个部分。如下图所示:
image
我们须要遍历一次输入的二维网格 grid,在 单元格内单元格间 进行合并。

单元格内:

  • 如果是空格:合并 0、1、2、3;
  • 如果是斜杠:合并 0、3,合并 1、2;
  • 如果是反斜杠:合并 0、1,合并 2、3。

单元格间:
把每一个单元格拆分成 4 个小三角形以后,相邻的单元格须要合并,无须分类讨论。 我们选择在遍历 grid 的每一个单元格的时候,分别「向右、向下」尝试合并。
image

  • 向右:合并 1 (当前单元格)和 3(当前单元格右边 1 列的单元格),上图中红色部分;
  • 向下:合并 2 (当前单元格)和 0(当前单元格下边 1 列的单元格),上图中蓝色部分。

事实上,大家选择在遍历 grid 的每一个单元格的时候,分别「向左、向上」、「向左、向下」、「向右、向上」、「向右、向下」中的任何一种都可以。

合并完成以后,并查集里连通分量的个数就是题目要求的区域的个数。


public class Solution {

    public int regionsBySlashes(String[] grid) {
        int N = grid.length;
        int size = 4 * N * N;

        UnionFind unionFind = new UnionFind(size);
        for (int i = 0; i < N; i++) {
            char[] row = grid[i].toCharArray();
            for (int j = 0; j < N; j++) {
                // 二维网格转换为一维表格,index 表示将单元格拆分成 4 个小三角形以后,编号为 0 的小三角形的在并查集中的下标
                int index = 4 * (i * N + j);
                char c = row[j];
                // 单元格内合并
                if (c == '/') {
                    // 合并 0、3,合并 1、2
                    unionFind.union(index, index + 3);
                    unionFind.union(index + 1, index + 2);
                } else if (c == '\\') {
                    // 合并 0、1,合并 2、3
                    unionFind.union(index, index + 1);
                    unionFind.union(index + 2, index + 3);
                } else {
                    unionFind.union(index, index + 1);
                    unionFind.union(index + 1, index + 2);
                    unionFind.union(index + 2, index + 3);
                }

                // 单元格间合并
                // 向右合并:1(当前)、3(右一列)
                if (j + 1 < N) {
                    unionFind.union(index + 1, 4 * (i * N + j + 1) + 3);
                }
                // 向下合并:2(当前)、0(下一行)
                if (i + 1 < N) {
                    unionFind.union(index + 2, 4 * ((i + 1) * N + j));
                }
            }
        }
        return unionFind.getCount();
    }

    private class UnionFind {

        private int[] parent;

        private int count;

        public int getCount() {
            return count;
        }

        public UnionFind(int n) {
            this.count = n;
            this.parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            while (x != parent[x]) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }
        // 这里的union和find的逻辑我没看懂,mark!!
        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return;
            }

            parent[rootX] = rootY;
            count--;
        }
    }
}
0

评论区