• 并查集理论及常见面试题

    并查集理论及常见面试题

    1 并查集理论

    1）有若干个样本a、b、c、d…类型假设都是V
    2）在并查集中一开始认为每个样本都在单独的集合里
    3）用户可以在任何时候调用如下两个方法：

    • boolean isSameSet（V x， V y）：查询样本x和样本y是否属于一个集合
    • void union（V x， V y）：把x和y各自所在集合的所有样本合并成一个集合

    4）isSameSet和union方法的代价越低越好
    5）每个节点都有一条往上指的指针
    6）节点a往上找到的头节点，叫做a所在集合的代表节点
    7）查询x和y是否属于同一个集合，就是看看找到的代表节点是否是同一个
    8）把x和y各自所在集合的所有点合并成一个集合，只需要小集合的代表点挂在大集合的代表点的下方即可

    2 并查集的优化及应用场景

    2.1 并查集的优化

    1. 节点往上找代表节点的过程，把沿途的链变成扁平的
    2. 小集合挂在大集合的下面
    3. 如果方法调用很频繁，则有结论：单次调用的代价为O（1），两个方法都是如此

    2.2 应用场景

    • 解决两大块区域的合并问题
    • 图领域

    3 并查的实现【哈希表】

    3.1 定义节点类

    并查集中每个集合中的元素

    //定义节点类[并差集中的组成部分]
public static class Node<V>{
    private V value;
    public Node(V value){
        this.value = value;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    3.2 定义并查集类

    主要有三个属性：并查集中集合的所有元素、每个集合中元素所对应的父节点，每个节点所包含的子节点数

    //并查集类
public static class UnionFind<V>{
    //该节点下所对应的节点
    public HashMap<V, Node<V>> nodes;
    //该节点对应的父节点
    public HashMap<Node<V>, Node<V>> parents;
    //以该节点为集合，所包含的元素个数
    public HashMap<Node<V>, Integer> sizeMap;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    3.3 findFather(Node cur)寻找该节点的父节点

    /**
  * 找到父节点【给你一个节点，请你往上到不能再往上，把代表节点返回】
  * @param cur
  * @return
  */
 public Node<V> findFather(Node<V> cur){
     Stack<Node<V>> path = new Stack<>();
     while(cur != parents.get(cur)){
         //只要当前节点不是该节点对应父节点,就一级一级往上找
         path.push(cur);
         cur = parents.get(cur);
     }
     while(!path.isEmpty()){
         //将沿途的链变成扁平的
         parents.put(path.pop(), cur);
     }
     return cur;
 }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    3.4 isSameSet(V a, V b)判断两个节点是否在同一个集合

    注意：集合中，默认元素值不重复

    /**
  * 是否在一个集合
  * @param a
  * @param b
  * @return
  */
 public boolean isSameSet(V a, V b){
     //看是否是同一个代表节点
     return findFather(nodes.get(a)) == findFather(nodes.get(b));
 }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    3.5 union(V a, V b)聚合方法

    /**
 * 合并，聚合
 * @param a
 * @param b
 */
public void union(V a, V b){
    Node<V> aHead = findFather(nodes.get(a));
    Node<V> bHead = findFather(nodes.get(b));
    if(aHead != bHead){
        //两个集合不再一块，小的主动合并大的【小的代表节点放在大的代表节点下面】
        int aSetSize = sizeMap.get(aHead);
        int bSetSize = sizeMap.get(bHead);
        Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
        Node<V> small = big == aHead ? bHead : aHead;
        //小的父节点事大的
        parents.put(small, big);
        sizeMap.put(big, aSetSize + bSetSize);
        sizeMap.remove(small);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    3.6 sets()集合中的所有节点数

    /**
  * 该并查集包含的所有节点数
  * @return
  */
 public int sets(){
     return sizeMap.size();
 }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    3.7 全部代码

    /**
 * 并查集【哈希表实现】
 */
public class UnionFindDemo {

    //定义节点类[并差集中的组成部分]
    public static class Node<V> {
        private V value;

        public Node(V value) {
            this.value = value;
        }
    }


    //并查集类
    public static class UnionFind<V> {
        //该节点下所对应的节点
        public HashMap<V, Node<V>> nodes;
        //该节点对应的父节点
        public HashMap<Node<V>, Node<V>> parents;
        //以该节点为集合，所包含的元素个数
        public HashMap<Node<V>, Integer> sizeMap;

        /**
         * 找到父节点【给你一个节点，请你往上到不能再往上，把代表节点返回】
         *
         * @param cur
         * @return
         */
        public Node<V> findFather(Node<V> cur) {
            Stack<Node<V>> path = new Stack<>();
            while (cur != parents.get(cur)) {
                //只要当前节点不是该节点对应父节点,就一级一级往上找
                path.push(cur);
                cur = parents.get(cur);
            }
            while (!path.isEmpty()) {
                //将沿途的链变成扁平的
                parents.put(path.pop(), cur);
            }
            return cur;
        }

        /**
         * 是否在一个集合
         *
         * @param a
         * @param b
         * @return
         */
        public boolean isSameSet(V a, V b) {
            //看是否是同一个代表节点
            return findFather(nodes.get(a)) == findFather(nodes.get(b));
        }

        /**
         * 合并，聚合
         *
         * @param a
         * @param b
         */
        public void union(V a, V b) {
            Node<V> aHead = findFather(nodes.get(a));
            Node<V> bHead = findFather(nodes.get(b));
            if (aHead != bHead) {
                //两个集合不再一块，小的主动合并大的【小的代表节点放在大的代表节点下面】
                int aSetSize = sizeMap.get(aHead);
                int bSetSize = sizeMap.get(bHead);
                Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
                Node<V> small = big == aHead ? bHead : aHead;
                //小的父节点事大的
                parents.put(small, big);
                sizeMap.put(big, aSetSize + bSetSize);
                sizeMap.remove(small);
            }
        }

        /**
         * 该并查集包含的所有节点数
         *
         * @return
         */
        public int sets() {
            return sizeMap.size();
        }
    }

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89

    4 面试常考题目（LeetCode）

    4.1 LeetCode - 541：省份数量（朋友圈的个数）

    在这里插入图片描述

    4.1.1 思路：

    因为如果1,2之间认识，那么2,1一定认识，所以利用并查集的时候只需要遍历右上部分即可

    4.1.2 代码：
    //利用并查集求解
class Solution {
    public static int findCircleNum(int[][] isConnected) {
        int N = isConnected.length;
        //为每列创建集合{0} {1} ... {N - 1}
        UnionFind unionFind = new UnionFind(N);
        for(int i = 0; i < N; ++i){
            for(int j = i + 1; j < N; ++j){
                //互相认识【合并】
                if(isConnected[i][j] == 1){
                    unionFind.union(i, j);
                }
            }
        }
        //返回并查集中集合个数
        return unionFind.sets();
    }
    
    public static class UnionFind {
        //每个集合的代表节点
        private int[] parent;
        //每个集合中元素的个数
        private int[] size;
        //类比于栈【辅助】
        private int[] help;
        //并查集中集合的个数
        private int sizes;
        
        public UnionFind(int N){
            this.parent = new int[N];
            this.size = new int[N];
            this.sizes = N;
            //按照最大额度算
            this.help = new int[N];
            for(int i = 0; i < N; i++){
                parent[i] = i;
                //最开始只有它自己
                size[i] = 1;
            }
        }
        
        //找该节点的代表节点【父亲节点】,并且铺平
        public int findFather(int cur){
            int index = 0;
            while(cur != parent[cur]){
                help[index++] = cur;
                cur = parent[cur];
            }
            //类比栈的操作【第一个index--：找到代表节点的下一个  第二个index--：依次往下遍历，将路径上的每一个节点的父都设为cur代表节点】
            for(index--; index >= 0; index--){
                parent[help[index]] = cur;
            }
            return cur;
        }
        
        public void union(int i, int j){
            int head1 = findFather(i);
            int head2 = findFather(j);
            if(parent[head1] != parent[head2]){
                if(size[head1] >= size[head2]){
                    //head1 大：head2主动合并
                    parent[head2] = parent[head1];
                    size[head1] += size[head2];
                } else {
                    parent[head1] = parent[head2];
                    size[head2] += size[head1];
                }
                //每次合并完之后，size--
                sizes--;
            }
        }
        
        public int sets(){
            return sizes;
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77

    4.2 LeetCode - 岛屿的最大面积

    在这里插入图片描述

    4.2.1 解法一：infect，感染法
    //方法一：感染法infect
class Solution {
    public int numIslands(char[][] grid) {
        //岛屿数量
        int lands = 0;
        for(int i = 0; i < grid.length; ++i){
            for(int j = 0; j < grid[i].length; ++j){
                //如果为1，则感染【上下左右】，感染后变成0
                if(grid[i][j] == '1'){
                    lands++;
                    infect(grid, i, j);
                }
            }
        }
        return lands;
    }
    //感染方法infect
    public void infect(char[][] grid, int i, int j){
        //边界条件【是否超出范围】或不满足条件
        if(i < 0 || i > grid.length - 1 || j < 0 || j > grid[0].length - 1 || grid[i][j] != '1'){
            return;
        }
        //感染之后
        grid[i][j] = '0';
        infect(grid, i - 1, j);
        infect(grid, i, j - 1);
        infect(grid, i, j + 1);
        infect(grid, i+1, j);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    4.2.2 解法二：利用并查集
    //并查集：将行列转换为角标
class Solution {
    public int numIslands(char[][] board) {
        int row = board.length;
        int col = board[0].length;
        UnionFind unionFind = new UnionFind(board);
        //处理第一行
        for(int j = 1; j < col; j++){
            if(board[0][j-1] == '1' && board[0][j] == '1'){
                unionFind.union(0, j-1, 0, j);
            }
        }
        //处理第一列
        for(int i = 1; i < row; i++){
            if(board[i-1][0] == '1' && board[i][0] == '1'){
                unionFind.union(i-1, 0, i, 0);
            }
        }
        for(int i = 1; i < row; i++){
            for(int j = 1; j < col; j++){
                if(board[i][j] == '1'){
                    if(board[i][j-1] == '1'){
                        unionFind.union(i, j-1, i,j);
                    }
                    if(board[i-1][j] == '1'){
                        unionFind.union(i-1, j, i, j);
                    }
                }
            }
        }
        return unionFind.sets();
    }
    public static class UnionFind{
        //父节点
        private int[] parent;
        //每个节点的子节点
        private int[] size;
        //辅助数组，类比栈
        private int[] help;
        //列数
        private int col;
        //并查集中集合个数
        private int sizes;
        
        public UnionFind(char[][] board){
            col = board[0].length;
            sizes = 0;
            int row = board.length;
            int len = row * col;
            parent = new int[len];
            size = new int[len];
            help = new int[len];
            for(int r = 0; r < row; r++){
                for(int c = 0; c < col; c++){
                    //只给有1的创建集合
                    if(board[r][c] == '1'){
                        int i = index(r, c);
                        parent[i] = i;
                        size[i] = 1;
                        sizes++;
                    }
                }
            }
        }
        
        public int index(int r, int c){
            //注意col是不变的
            return r * col + c;
        }
        
        
        //原始位置 -> 下标
        public int findFather(int i){
            int index = 0;
            while(i != parent[i]){
                help[index++] = i;
                i = parent[i];
            }
            for(index--; index >= 0; index--){
                parent[help[index]] = i;
            }
            return i;
        }
        
        
        public void union(int row1, int col1, int row2, int col2){
            int i1 = index(row1, col1);
            int i2 = index(row2, col2);
            int f1 = findFather(i1);
            int f2 = findFather(i2);
            if(f1 != f2){
                if(size[f1] >= size[f2]){
                    parent[f2] = f1;
                    size[f1] += size[f2];
                } else {
                    parent[f1] = f2;
                    size[f2] += size[f1];
                }
                sizes--;
            }
        }
            
        public int sets(){
            return sizes;
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107

    拓展：也可以用一个类代替1，只要不重复就可以

    部分代码如下：

    public static class Dot {

}


public static class Node<V> {

	V value;

	public Node(V v) {
		value = v;
	}

}

public static class UnionFind1<V> {
	public HashMap<V, Node<V>> nodes;
	public HashMap<Node<V>, Node<V>> parents;
	public HashMap<Node<V>, Integer> sizeMap;

	public UnionFind1(List<V> values) {
		nodes = new HashMap<>();
		parents = new HashMap<>();
		sizeMap = new HashMap<>();
		for (V cur : values) {
			Node<V> node = new Node<>(cur);
			nodes.put(cur, node);
			parents.put(node, node);
			sizeMap.put(node, 1);
		}
	}

	public Node<V> findFather(Node<V> cur) {
		Stack<Node<V>> path = new Stack<>();
		while (cur != parents.get(cur)) {
			path.push(cur);
			cur = parents.get(cur);
		}
		while (!path.isEmpty()) {
			parents.put(path.pop(), cur);
		}
		return cur;
	}

	public void union(V a, V b) {
		Node<V> aHead = findFather(nodes.get(a));
		Node<V> bHead = findFather(nodes.get(b));
		if (aHead != bHead) {
			int aSetSize = sizeMap.get(aHead);
			int bSetSize = sizeMap.get(bHead);
			Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
			Node<V> small = big == aHead ? bHead : aHead;
			parents.put(small, big);
			sizeMap.put(big, aSetSize + bSetSize);
			sizeMap.remove(small);
		}
	}

	public int sets() {
		return sizeMap.size();
	}

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63

    4.3 LeetCode 305 - 岛屿问题扩展

    给一个二维数组，[[2,3], [4,1], [5,6]],每次空降1，第一次让2,3位置变成1，第二次让4,1位置变成1，每次空降都应该返回一个结果（岛屿的数量），比如，空降三次，结果应为[2,3,5]

    4.3.1 定义并查集
    public static class UnionFind1 {
        private int[] parent;
        private int[] size;
        private int[] help;
        private final int row;
        private final int col;
        private int sets;

        public UnionFind1(int m, int n) {
            row = m;
            col = n;
            sets = 0;
            int len = row * col;
            parent = new int[len];
            size = new int[len];
            help = new int[len];
        }
 }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    4.3.2 定义映射下标index
     /**
  * 映射下标【r*col+c】，注意是col
  * @param r
  * @param c
  * @return
  */
 private int index(int r, int c) {
     return r * col + c;
 }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    4.3.3 定义find找寻自己的代表节点（父节点）
    /**
 * 找代表节点【父亲】
 * @param i
 * @return
 */
private int find(int i) {
    int hi = 0;
    while (i != parent[i]) {
        help[hi++] = i;
        i = parent[i];
    }
    for (hi--; hi >= 0; hi--) {
        parent[help[hi]] = i;
    }
    return i;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    4.3.4 定义合并方法
    /**
 * 合并
 * @param r1
 * @param c1
 * @param r2
 * @param c2
 */
private void union(int r1, int c1, int r2, int c2) {
    if (r1 < 0 || r1 == row || r2 < 0 || r2 == row || c1 < 0 || c1 == col || c2 < 0 || c2 == col) {
        return;
    }
    int i1 = index(r1, c1);
    int i2 = index(r2, c2);
    if (size[i1] == 0 || size[i2] == 0) {
        return;
    }
    int f1 = find(i1);
    int f2 = find(i2);
    if (f1 != f2) {
        if (size[f1] >= size[f2]) {
            size[f1] += size[f2];
            parent[f2] = f1;
        } else {
            size[f2] += size[f1];
            parent[f1] = f2;
        }
        sets--;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    4.3.5 定义连接方法【在节点上下左右都去寻找，看能否合并】
    /**
 * 连接
 * @param r
 * @param c
 * @return
 */
public int connect(int r, int c) {
    int index = index(r, c);
    //看该位置上是否已经空降过，如果没有，就初始化，如果有，直接返回
    if (size[index] == 0) {
        parent[index] = index;
        size[index] = 1;
        sets++;
        union(r - 1, c, r, c);
        union(r + 1, c, r, c);
        union(r, c - 1, r, c);
        union(r, c + 1, r, c);
    }
    return sets;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    4.3.6 整体代码流程
    
/**
 * 岛屿问题扩展[空降1]，动态生成，节约空间
 */
public class NumberOfIsLandTwo {
    
    public static List<Integer> numIslands21(int m, int n, int[][] positions) {
        UnionFind1 uf = new UnionFind1(m, n);
        List<Integer> ans = new ArrayList<>();
        //对于每一次的空降1，都生成一个结果，并返回
        for (int[] position : positions) {
            ans.add(uf.connect(position[0], position[1]));
        }
        return ans;
    }

    public static class UnionFind1 {
        private int[] parent;
        private int[] size;
        private int[] help;
        private final int row;
        private final int col;
        private int sets;

        public UnionFind1(int m, int n) {
            row = m;
            col = n;
            sets = 0;
            int len = row * col;
            parent = new int[len];
            size = new int[len];
            help = new int[len];
        }

        /**
         * 映射下标【r*col+c】，注意是col
         * @param r
         * @param c
         * @return
         */
        private int index(int r, int c) {
            return r * col + c;
        }

        /**
         * 找代表节点【父亲】
         * @param i
         * @return
         */
        private int find(int i) {
            int hi = 0;
            while (i != parent[i]) {
                help[hi++] = i;
                i = parent[i];
            }
            for (hi--; hi >= 0; hi--) {
                parent[help[hi]] = i;
            }
            return i;
        }

        /**
         * 合并
         * @param r1
         * @param c1
         * @param r2
         * @param c2
         */
        private void union(int r1, int c1, int r2, int c2) {
            if (r1 < 0 || r1 == row || r2 < 0 || r2 == row || c1 < 0 || c1 == col || c2 < 0 || c2 == col) {
                return;
            }
            int i1 = index(r1, c1);
            int i2 = index(r2, c2);
            if (size[i1] == 0 || size[i2] == 0) {
                return;
            }
            int f1 = find(i1);
            int f2 = find(i2);
            if (f1 != f2) {
                if (size[f1] >= size[f2]) {
                    size[f1] += size[f2];
                    parent[f2] = f1;
                } else {
                    size[f2] += size[f1];
                    parent[f1] = f2;
                }
                sets--;
            }
        }

        /**
         * 连接
         * @param r
         * @param c
         * @return
         */
        public int connect(int r, int c) {
            int index = index(r, c);
            //看该位置上是否已经空降过，如果没有，就初始化，如果有，直接返回
            if (size[index] == 0) {
                parent[index] = index;
                size[index] = 1;
                sets++;
                union(r - 1, c, r, c);
                union(r + 1, c, r, c);
                union(r, c - 1, r, c);
                union(r, c + 1, r, c);
            }
            return sets;
        }

    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115

    注意：如果matrix极大，设计一种可行的并行计算方案
    思路：
    使用字符串，例如:“17_41239491374”
    核心代码：

    public int connect(int r, int c) {
	String key = String.valueOf(r) + "_" + String.valueOf(c);
	if (!parent.containsKey(key)) {
		parent.put(key, key);
		size.put(key, 1);
		sets++;
		String up = String.valueOf(r - 1) + "_" + String.valueOf(c);
		String down = String.valueOf(r + 1) + "_" + String.valueOf(c);
		String left = String.valueOf(r) + "_" + String.valueOf(c - 1);
		String right = String.valueOf(r) + "_" + String.valueOf(c + 1);
		union(up, key);
		union(down, key);
		union(left, key);
		union(right, key);
	}
	return sets;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
  • 相关阅读:
    Maven私服搭建Nexus3
    完美解决 Error: Cannot find module ‘@vue/cli-plugin-eslint‘ 报错
    C++算法题 - 矩阵
    在DevTool的源代码栏打开控制台界面
    ES6基础知识
    hivesql,sql 函数总结：
    浏览器的缓存机制 强制缓存 && 协商缓存
    Linux(Centos7版本中安装mysql5.7 遇到的各种问题，最后由于Centos7安装mysql5.7需要收费，安装了 mariadb 数据库）
    Kratos战神微服务框架（二）
    数据集笔记：Pems 自行下载数据+python处理
  • 原文地址：https://blog.csdn.net/weixin_45565886/article/details/126560307