130. 被围绕的区域

张伦聪zhangluncong

发布于 2022-10-26 18:29:41

3310

发布于 2022-10-26 18:29:41

文章被收录于专栏：张伦聪的技术博客张伦聪的技术博客

给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。

找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

示例:

X X X X
X O O X
X X O X
X O X X
运行你的函数后，矩阵变为：

X X X X
X X X X
X X X X
X O X X
解释:

被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

解：这题用到并查集算法，由点及面，来了解一下什么是并查集。

并查集定义 在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）定义了两个用于此数据结构的操作：

Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
Union：将两个子集合并成同一个集合。

动态连接（Dynamic connectivity）的问题

所谓的动态连接问题是指在一组可能相互连接也可能相互没有连接的对象中，判断给定的两个对象是否联通的一类问题。这类问题可以有如下抽象：

有一组构成不相交集合的对象

union: 联通两个对象
find: 返回两个对象之间是否存在一条联通的通路

在使用union-find处理动态连接的问题时，我们一般将这一组对象抽象为一个数组。对于这组对象，其中相互连接的一些对象构成的子集称为联通集。

算法目的：能够在如下条件下高效解决动态连接的问题

Union命令和Find命令可能交替被调用
操作的总数M可能很大
集合中的对象数目N可能很大

注释都在代码里，比较容易，findOld查找方法没有对并查集进行优化，如果树太高性能差，因此写了一个findNew方法，来提升性能，我们不需要关心树的具体结构是什么我们只关心如果查询性能快，因此可以对数结构进行破坏，重组。

纯手打并查集代码：

package com.zlc.jzlc;

public class UnionFind {
    //pre[i]保存的是i的上级
    private int[] pre;

    //初始化，每个人的上级就是他自己，自成一派,形成了n个独立的集合
    public void init(int n) {
        this.pre = new int[n];
        for (int i = 0; i < n; i++) {
            pre[i] = i;
        }
    }

    //合并p,q两个对象所在集合
    public void union(int p, int q) {
        int rootP = getRoot(p);
        int rootQ = getRoot(q);
        //任意赋值，也可以pre[rootP] = rootQ;
        //只要能并起来就行
        pre[rootQ] = rootP;
    }

    //在p所在集合中查找q是否归属于这个集合
    public boolean find(int p, int q) {
        int rootP = getRoot(p);
        int rootQ = getRoot(q);
        return rootP == rootQ;
    }

    //查找i的最顶级上级
    //随着集合构造的树高度越高，时间复杂度会变得越高
    //所以我们可以进行优化，每次进行查找根的时候，
    //直接上级直接改成根节点，这样树就变得更加扁平
    //提升查找速度
    private int getRoot(int i) {
        int tmp = i;
        while (tmp != pre[tmp]) {
            tmp = pre[tmp];
        }
        pre[i] = tmp;
        return tmp;
    }

    public static void main(String[] args) {
        UnionFind unionFind = new UnionFind();
        //初始化10个独立集合
        unionFind.init(10);
        //将1所在集合，2所在集合组成一个集合，结果1，2
        unionFind.union(1, 2);
        //将3所在集合，4所在集合组成一个集合，结果3，4
        unionFind.union(3, 4);
        //将1所在集合，3所在集合组成一个集合，结果1，2，3，4
        unionFind.union(1, 3);
        //将5所在集合，6所在集合组成一个集合，结果5，6
        unionFind.union(5, 6);
        unionFind.find(4, 6);
        unionFind.find(2, 4);
    }

}

了解了并查集的基本原理，这题也就解出来了

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        int row = board.length;
        int col = board[0].length;
        UnionFind uf = new UnionFind();
        uf.init(row * col + 1);
        //虚拟节点
        int dummy = row * col;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 'O') {
                    if (i == 0 || i == row - 1 || j == 0 || j == col - 1) {//边界的0全部连接到虚拟集合
                        uf.union(node(col, i, j), dummy);
                    } else {//非边界的0看上下左右是否有，有的话连接起来
                        if (board[i - 1][j] == 'O') {
                            uf.union(node(col, i, j), node(col, i - 1, j));
                        }
                        if (board[i + 1][j] == 'O') {
                            uf.union(node(col, i, j), node(col, i + 1, j));
                        }
                        if (board[i][j - 1] == 'O') {
                            uf.union(node(col, i, j), node(col, i, j - 1));
                        }
                        if (board[i][j + 1] == 'O') {
                            uf.union(node(col, i, j), node(col, i, j + 1));
                        }
                    }
                }
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (uf.find(dummy, node(col, i, j))) {
                    board[i][j] = 'O';
                } else {
                    board[i][j] = 'X';
                }
            }
        }
    }

    private int node(int col, int i, int j) {
        return i * col + j;
    }
}

public class UnionFind {
    //pre[i]保存的是i的上级
    private int[] pre;

    //初始化，每个人的上级就是他自己，自成一派,形成了n个独立的集合
    public void init(int n) {
        this.pre = new int[n];
        for (int i = 0; i < n; i++) {
            pre[i] = i;
        }
    }

    //合并p,q两个对象所在集合
    public void union(int p, int q) {
        int rootP = getRoot(p);
        int rootQ = getRoot(q);
        //任意赋值，也可以pre[rootP] = rootQ;
        //只要能并起来就行
        pre[rootQ] = rootP;
    }

    //在p所在集合中查找q是否归属于这个集合
    public boolean find(int p, int q) {
        int rootP = getRoot(p);
        int rootQ = getRoot(q);
        return rootP == rootQ;
    }

    //查找i的最顶级上级
    //随着集合构造的树高度越高，时间复杂度会变得越高
    //所以我们可以进行优化，每次进行查找根的时候，
    //直接上级直接改成根节点，这样树就变得更加扁平
    //提升查找速度
    private int getRoot(int i) {
        int tmp = i;
        while (tmp != pre[tmp]) {
            tmp = pre[tmp];
        }
        pre[i] = tmp;
        return tmp;
    }

    public static void main(String[] args) {
        UnionFind unionFind = new UnionFind();
        //初始化10个独立集合
        unionFind.init(10);
        //将1所在集合，2所在集合组成一个集合，结果1，2
        unionFind.union(1, 2);
        //将3所在集合，4所在集合组成一个集合，结果3，4
        unionFind.union(3, 4);
        //将1所在集合，3所在集合组成一个集合，结果1，2，3，4
        unionFind.union(1, 3);
        //将5所在集合，6所在集合组成一个集合，结果5，6
        unionFind.union(5, 6);
        unionFind.find(4, 6);
        unionFind.find(2, 4);
    }

}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018-09-17，如有侵权请联系 cloudcommunity@tencent.com 删除

algorithm