0%

并查集

发表于 分类于

文章字数：844,阅读全文大约需要3分钟

介绍

并查集是一种管理元素分组的数据结构，可以管理一系列不相交的集合。
并查集支持两种元素操作

  1. 合并Union, 将两个集合并为一个集合
  2. 查询Find, 查询两个元素是否在同一个集合中

并查集的原理就是选取一个元素作为整个集合的父节点（代表节点），所以如果两个元素一直向上查找父节点，最后的根节点一样，则这两个元素在同一个集合中。合并的原理也一样，将其中一个元素集合的父节点设置为另一个元素集合的父节点，这样两个元素所在的集合就有共同的父节点。

移除最多同行或同列的石头

leetcode第947题

题目：
n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。
如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。
给你一个长度为n的数组stones，其中stones[i] = [xi, yi]表示第i块石头的位置，返回 可以移除的石子 的最大数量。

思路：
只要同行或同列里存在其他石子，则当前的石子就可以被移除
可以把同行或同列有相交的石子连起来，组成一个集合
则棋盘上会有若干集合，每个集合都可以按顺序移除石子，直到只剩一个
所以，有多少个这种集合，最少就能剩下几个石子
用石子总数减去集合数，就是最多移除的石子数
查找集合就可以使用并查集，将相交的石子所在的集合合并，最后查找有几个并查集就可以了

解

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
public int removeStones(int[][] stones) {
    // 父节点集合，代表每个元素的父节点
    int[] fathers = new int[stones.length];
    // 初始化集合，设置每个元素为一个单独的集合，即父节点是自己
    for (int i = 0; i < fathers.length; i++) {
        // 父节点是自己
        fathers[i] = i;
    }
    // 循环所有石子，如果在一行或者一列，则并集
    for (int i = 0; i < stones.length; i++) {
        for (int j = i + 1; j < stones.length; j++) {
            if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
                join(fathers, i, j);
            }
        }
    }
    // 查找一下fathers里每个元素的父级，最后统计一下有几个集合。
    // 总数-集合数就是结果
    return stones.length - (int)Arrays.stream(fathers).map(val -> findFather(fathers, val)).distinct().count();
}

/**
 * 合并操作
 * 
 * @param fathers 父节点集合
 * @param i
 * @param j
 */
private void join(int[] fathers, int i, int j) {
    // 如果i和j所在的集合的父节点不一样，则代表是两个集合，需要合并
    if (findFather(fathers, i) != findFather(fathers, j)) {
        // 其中一个集合的父节点设置父节点为另一个集合的父节点
        fathers[findFather(fathers, j)] = findFather(fathers, i);
    }
}

/**
 * 查找父节点
 * 
 * @param fathers
 * @param x
 * @return
 */
private int findFather(int[] fathers, int x) {
    // 如果父节点不是集合的根节点（集合的父节点）
    while (fathers[x] != x) {
        // 设置当前节点的父节点为父节点的父节点，减少下次查询的次数。也可以在查找到根节点后将路径上所有的节点父节点都设置成集合根节点
        fathers[x] = fathers[fathers[x]];
        // 向上查找
        x = fathers[x];
    }
    return x;
}

验证, 写了一个将leetcode测试用例数组转换成java数组的小工具

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void main(String[] args) {
    String data = "[[0,1],[1,0],[1,1]]";
    data = delChar(data);
    final String[] dataSplit = data.split(",\\[");
    int[][] stones = new int[dataSplit.length][2];
    for (int i = 0; i < stones.length; i++) {
        int[] one = new int[2];
        String oneData = dataSplit[i].replace("[", "");
        oneData = oneData.replace("]", "");
        one[0] = Integer.parseInt(StringUtils.split(oneData, ",")[0]);
        one[1] = Integer.parseInt(StringUtils.split(oneData, ",")[1]);
        stones[i] = one;
    }
    Solution solution = new Solution();
    System.out.println(solution.removeStones(stones));
}

public static String delChar(String data) {
    return StringUtils.substring(data, 1, data.length() - 1);
}