[并查集]并查集应用之打砖块

继续并查集！

题目

打砖块

有一个 m x n 的二元网格，其中 1 表示砖块，0 表示空白。砖块 稳定（不会掉落）的前提是：

一块砖直接连接到网格的顶部，或者
至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时
给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而掉落。一旦砖块掉落，它会立即从网格中消失（即，它不会落在其他稳定的砖块上）。

返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。

注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。

示例1
输入：grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
输出：[2]
解释：
网格开始为：
[[1,0,0,0]， [1,1,1,0]]
消除 (1,0) 处加粗的砖块，得到网格：
[[1,0,0,0] [0,1,1,0]]
两个加粗的砖不再稳定，因为它们不再与顶部相连，也不再与另一个稳定的砖相邻，因此它们将掉落。得到网格：
[[1,0,0,0], [0,0,0,0]]
因此，结果为 [2] 。

示例2
输入：grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
输出：[0,0]
解释：
网格开始为：
[[1,0,0,0], [1,1,0,0]]
消除 (1,1) 处加粗的砖块，得到网格：
[[1,0,0,0], [1,0,0,0]]
剩下的砖都很稳定，所以不会掉落。网格保持不变：
[[1,0,0,0], [1,0,0,0]]
接下来消除 (1,0) 处加粗的砖块，得到网格：
[[1,0,0,0], [0,0,0,0]]
剩下的砖块仍然是稳定的，所以不会有砖块掉落。
因此，结果为 [0,0] 。

分析

一开始我的想法有点跑偏，从正向考虑，想通过并查集给每个分量维护一个屋顶连接数，然后打掉砖块的时候这个连接数减一，然后在遍历分量去搜索连接数为0的分量做统计，但是这么做代码越写越复杂，最后还是放弃了，采用了官方的逆向的思路。

题目拆解

正向拆解

1、有一个矩阵存放了若干个分量，标记为1代表此处有链接，标记为0代表此处无连接；

2、从屋顶开始走，如果可以走到某一个分量，该分量和屋顶相连，不会掉落；

3、每次进行一次敲击动作，检查有多少个分量失去了与屋顶的链接，返回这个数量；

简单来说，题目就是这三步，从题目正向来看，是一个把连通树，不断拆解的过程，每次敲击，要对原有的树进行一次拆分，看看拆分后，原有树还有多少个分量。

但是，并查集的主要能力是合并和查找，所以拆分并不是并查集这种数据结构擅长的能力。不过如果反过来想，我们先把敲击动作全部执行完，然后往回一步一步复原原本的树，这样的操作就是一个合并的操作，也就得到了并查集擅长的连通性判断的领域。

以这个思路重新拆解一下题目

逆向拆解

1、有一个矩阵存放了若干个分量，标记为1代表此处有链接，标记为0代表此处无连接；

2、从屋顶开始走，如果可以走到某一个分量，该分量和屋顶相连，不会掉落；

3、每次在矩阵中进行一次粘合操作，检查粘合后，有多少个分量因为这次粘合而被链接到了屋顶。

逆向拆解之后，题目就变得清晰很多。

继续进行解题步骤的分析

分析步骤

1、整个矩阵所有点可以看做是一个链接到屋顶的树，本次并查集只有一个树。

2、矩阵中的每一个点都是一个分量，额外定义一个分量用来标记屋顶。

3、合并操作前置有二，1）如果在第一排，需要和屋顶合并；2）相连的分量进行合并

4、为分量添加一个连接数属性，标识以当前分量为根节点的分量有多少。

5、每次合并操作后，以屋顶为根节点的分量增加了多少，即代表经过本次粘合动作新增了多少分量。

解题步骤

1、定制并查集，增加以当前分量为根节点的分量总数属性

2、复制一个矩阵，执行所有的hit操作，得到一个最终矩阵，即为逆向的初始矩阵。

3、初始化并查集，将逆向的初始矩阵进行合并操作

4、每次粘合一个连接点，判断是否需要合并操作并执行。

5、获取合并前后与屋顶链接的分量总数，做差并记录结果。

代码实现

并查集构建

class HitBricksUnionFind {

    // 存储连分量
    protected int[] id;
    // 当前并查集不同的连通分量总数
    protected int count;
    // 分量权重数组,数组里的值代表当前分量下的分量数量
    private int[] weightArr;

    public HitBricksUnionFind(int n) {
        // 初始化时,没个分量互不连通
        this.count = n;
        // 初始化一个容纳全量分量的数组
        this.id = new int[n];
        for (int i = 0; i < n; i++) {
            // 没个分量初始值指向自身
            id[i] = i;
        }
        weightArr = new int[n];
        // 初始化权重数组,初始化是每个分量下的权重都为1
        for (int i = 0; i < weightArr.length; i++) {
            weightArr[i] = 1;
        }
    }

    void union(int p, int q) {
        // 找到p的标识
        int pId = find(p);
        // 找到q的标识
        int qId = find(q);

        // 如果两个标识相等,代表已经合并
        if (pId == qId) return;

        // 将权重小的树,合并到权重大的树下
        if (weightArr[pId] < weightArr[qId]) {
            id[pId] = qId;
            weightArr[qId] += weightArr[pId];
        } else {
            id[qId] = pId;
            weightArr[pId] += weightArr[qId];
        }

        // 每次合并操作,会降低一个不同分量组
        count--;
    }

    int find(int p) {
        if (p == id[p]) return p;
        // 递归直接找到根节点,将分量直接指向根节点,完成彻底的路径压缩.
        id[p] = find(id[p]);
        return id[p];
    }

    /**
     * 获取以屋顶为根节点的分量总数
     *
     * @param p
     * @return
     */
    int getWeight(int p) {
        int root = find(p);
        return weightArr[root];
    }
}

算法代码

class Solution {

    private static int rowCount = 0;
    private static int colCount = 0;

    public static int[] hitBricks(int[][] grid, int[][] hits) {

        rowCount = grid.length;
        colCount = grid[0].length;

        // 一 构建逆向的初始数组
        // 1.1 将数据集copy一份
        int[][] tenet = new int[rowCount][colCount];
        for (int i = 0; i < tenet.length; i++) {
            for (int j = 0; j < tenet[i].length; j++) {
                tenet[i][j] = grid[i][j];
            }
        }
        // 1.2 执行hit操作,把所有点打掉
        for (int[] hit : hits) {
            tenet[hit[0]][hit[1]] = 0;
        }

        // 二 初始化并查集
        // 矩阵分量总数为 rowCount * colCount,+1代表额外预留出屋顶这个虚拟分量的位置
        int size = rowCount * colCount;
        HitBricksUnionFind uf = new HitBricksUnionFind(size + 1);
        // 2.1 先把第一排分量和屋顶进行合并操作
        for (int i = 0; i < tenet[0].length; i++) {
            if (tenet[0][i] == 1) {
                uf.union(getUfIndex(0, i), size);
            }
        }

        // 2.2 从第二排开始,合并链接的分量;1)与左侧连通;2)与上方连通
        for (int i = 1; i < tenet.length; i++) {
            for (int j = 0; j < tenet[i].length; j++) {

                if (tenet[i][j] == 1) {
                    // 有分量的地方才需要连通
                    if (tenet[i - 1][j] == 1) {
                        // 如果上方也有砖块,进行合并
                        uf.union(getUfIndex(i, j), getUfIndex(i - 1, j));
                    }
                    if (j > 0 && tenet[i][j - 1] == 1) {
                        // 如果左侧方也有砖块,进行合并
                        uf.union(getUfIndex(i, j), getUfIndex(i, j - 1));
                    }
                }
            }
        }

        // 三 执行粘合操作,粘合操作即为hit操作的逆向,将hits倒叙遍历
        // 3.1 定义四个方向
        int[][] dir = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        int[] res = new int[hits.length];


        for (int k = hits.length - 1; k >= 0; k--) {
            int[] hit = hits[k];
            int i = hit[0];
            int j = hit[1];
            // 3.2 如果原有数据集敲击位置为0,说明原本敲空,不需要粘合
            if (grid[i][j] == 0) continue;
            int totalCount = uf.getWeight(size);

            if (i == 0) {
                uf.union(j, size);
            }

            // 3.3 四个方向在没有越界的情况下,如果有砖块就合并

            for (int[] ints : dir) {
                int m = ints[0];
                int n = ints[1];
                int x = i + m;
                int y = j + n;
                if (inArea(x, y) && tenet[x][y] == 1) {
                    uf.union(getUfIndex(x, y), getUfIndex(i, j));
                }
            }
            int totalCountNew = uf.getWeight(size);
            // 因为题目需要排除敲击出的砖块,所以需要减1,为了防止出现负数,与0去最大值.
            res[k] = Math.max(0, totalCountNew - totalCount - 1);
            // 3.4 将粘合位置补上砖块
            tenet[i][j] = 1;
        }
        return res;

    }

    private static int getUfIndex(int x, int y) {
        return x * colCount + y;
    }

    private static boolean inArea(int x, int y) {
        return x >= 0 && x < rowCount && y >= 0 && y < colCount;
    }

}