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

发表于 更新于
本文字数： 5k 阅读时长 ≈ 5 分钟

LeetCode每日一题，947. Most Stones Removed with Same Row or Column

先看题目描述

sBnLuQ.png

大意就是给定一个 stones 数组，代表 n 个石头的二维坐标，如果一块石头的同行或同列上有其他石头存在，那么就可以移除这块石头，问最多可以移除多少块石头

算法和思路

并查集

我们可以把二维平面上的石头视为点，若两个石头的横坐标或纵坐标相同，则视为它们之间有边，我们根据移除石头的规则，可以得知对于一个连通图，我们可以把一个连通图里的所有顶点根据规则删除到只剩一个顶点，于是最多可以删除的石头数就是所有石头的数量 - 连通分量的个数，问题就转化为了如何求给定图的连通分量个数

求连通分量个数我们可以通过并查集解决，我们创建两个哈希表 rows 和 cols，分别维护横坐标，纵坐标和在对应坐标上第一次出现的石头，以 stones[i] 为例，当遍历到 stones[i] 时，设其横坐标和纵坐标为 row 和 col，若哈希表 rows 中存在键 row，其对应的值为 key，则说明在 stones[i] 前存在横坐标为 row 的石头，第一个横坐标为 row 的石头为 stones[key]，于是我们将 i 合并到 key 所在的连通分量中；若哈希表 rows 中不存在键 row，则说明在 stones[i] 之前不存在横坐标为 row 的石头，将键值对 <row，i> 添加到哈希表 rows 中。对于纵坐标 col 和哈希表 cols 做相同处理。这样遍历完 stones 数组时连通分量就通过并查集构造完成了，统计连通分量个数，据此计算结果并返回即可

算法源码

下面是使用哈希表的代码

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
class Solution {
    public int removeStones(int[][] stones) {
        int n = stones.length;
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        Map<Integer, Integer> rows = new HashMap<>();
        Map<Integer, Integer> cols = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int row = stones[i][0];
            int col = stones[i][1];
            if (rows.containsKey(row)) {
                union(rows.get(row), i, parent);
            } else {
                rows.put(row, i);
            }
            if (cols.containsKey(col)) {
                union(cols.get(col), i, parent);
            } else {
                cols.put(col, i);
            }
        }
        int res= 0;
        for (int i = 0; i < n; i++) {
            if (parent[i] != i) {
                res++;
            }
        }
        return res;
    }

    private int find(int x, int[] parent) {
        if (x != parent[x]) {
            parent[x] = find(parent[x], parent);
        }
        return parent[x];
    }

    private void union(int a, int b, int[] parent) {
        int x = find(a, parent);
        int y = find(b, parent);
        parent[y] = parent[x];
    }
}

由于题目中限制了横坐标和纵坐标的范围为 0 ~ 10000，于是可以用数组代替哈希表，从而优化运行效率

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
class Solution {
    public int removeStones(int[][] stones) {
        int n = stones.length;
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        int[] rows = new int[10001];
        int[] cols = new int[10001];
        Arrays.fill(rows, -1);
        Arrays.fill(cols, - 1);
        for (int i = 0; i < n; i++) {
            int row = stones[i][0];
            int col = stones[i][1];
            if (rows[row] >= 0) {
                union(rows[row], i, parent);
            } else {
                rows[row] = i;
            }
            if (cols[col] >= 0) {
                union(cols[col], i, parent);
            } else {
                cols[col] = i;
            }
        }
        int res= 0;
        for (int i = 0; i < n; i++) {
            if (parent[i] != i) {
                res++;
            }
        }
        return res;
    }

    private int find(int x, int[] parent) {
        if (x != parent[x]) {
            parent[x] = find(parent[x], parent);
        }
        return parent[x];
    }

    private void union(int a, int b, int[] parent) {
        int x = find(a, parent);
        int y = find(b, parent);
        parent[y] = parent[x];
    }
}

下面这个是将并查集作为内部类的写法

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
class Solution {
    public int removeStones(int[][] stones) {
        int n = stones.length;
        int[] rows = new int[10001];
        int[] cols = new int[10001];
        Arrays.fill(rows, -1);
        Arrays.fill(cols, -1);
        UnionFind unionFind = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            int row = stones[i][0];
            int col = stones[i][1];
            if (rows[row] >= 0) {
                unionFind.union(rows[row], i);
            } else {
                rows[row] = i;
            }
            if (cols[col] >= 0) {
                unionFind.union(cols[col], i);
            } else {
                cols[col] = i;
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (unionFind.parent[i] != i) {
                res++;
            }
        }
        return res;
    }

    private class UnionFind {
        int[] parent;

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

        int find(int x) {
            if (x != parent[x]) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        void union(int a, int b) {
            int x = find(a);
            int y = find(b);
            parent[y] = x;
        }
    }
}