Leetcode: Most Stones Removed wi

题目

分析

乍看之下，有点摸不着头脑。稍微举几个简单的例子，就能发现其中的规律。
题目给出一个“相连”的概念，即行或者列相同，这里可以用坐标系来理解。
那么，首先分析一些基本情况：

• 当没有石头“相连”，那么无法做出符合题意的操作，是0；
• 只有2个石头“相连”，能做出1个操作；
• 3个石头“相连”，就是2个操作；
• 可见，如果一组有n个石头相连，那么操作数就是n-1；
• 假如有两组，一组2相连，一组3相连，它们互相之间并不干涉，最后结果就是分别能进行操作的数目相加；
• 假设总共有m个互不干涉的组，那么操作数总共就是(n(0)-1)+(n(1)-1)+...+(n(m-1)-1)，其中n(i)代表第i组的石头个数。因为总共的石头个数是给定的，假设为N，那么可得最后的操作数就是(n(0)+...+n(m-1))-m = N-m。也就是说，问题转化为求总共有多少个互不相干的组。
• 要解决这个问题，连通图就是一个很直接的想法。但问题来了，我们一般运用的连通图是1维的，这个是2维的，怎么弄？假如强行开2维连通图，需要解决很多小问题，不是一时半会能写出无bug代码的，因此不如尝试把2维转化为1维。
• 根据题意，坐标的x和y是需要区分开来的，因为两个石头(x1,y1)与(x2,y2)，x或者y相等属于相连，但x1=y2这种可不算。
• 最简洁的做法，就是把y加上一个值，让x和y不会重合就好。题目里给的值是10000.
• 构造图只需要连通单个石头本身的x与y+10000就行了。假如与之前某个石头“相连”，连通的时候自然会发现。
• 到这里，问题就解决了，参考代码如下：

// T:O(NlogN) S:O(N)
class Solution {
    public int removeStones(int[][] stones) {
        int N = stones.length;
        DSU dsu = new DSU(20000);

        for (int[] stone: stones)
            dsu.union(stone[0], stone[1] + 10000);

        Set<Integer> seen = new HashSet();
        for (int[] stone: stones)
            seen.add(dsu.find(stone[0]));

        return N - seen.size();
    }
}

class DSU {
    int[] parent;
    public DSU(int N) {
        parent = new int[N];
        for (int i = 0; i < N; ++i)
            parent[i] = i;
    }
    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    public void union(int x, int y) {
        parent[find(x)] = find(y);
    }
}