Leetcode 947 Most Stones Removed

1. 数岛屿问题

如果两个石头在同行或者同列，两个石头就是连接的。连在一起的石头，可以组成一个连通图。每一个连通图至少会剩下1个石头。
所以我们希望存在一种思路，每个连通图都只剩下1个石头。
这样这题就转化成了数岛屿的问题。

2. 朴素DFS

实际上做这道题，你并不需要去构造或者证明，移走石头的方案。有了step1里的思路，已经足够用dfs来解决这个问题了。

    def removeStones(self, points):
        rows = collections.defaultdict(set)
        cols = collections.defaultdict(set)
        for i, j in points:
            rows[i].add(j)
            cols[j].add(i)

        def dfsRow(i):
            seenR.add(i)
            for j in rows[i]:
                if j not in seenC:
                    dfsCol(j)

        def dfsCol(j):
            seenC.add(j)
            for i in cols[j]:
                if i not in seenR:
                    dfsRow(i)

        seenR, seenC = set(), set()
        islands = 0
        for i, j in points:
            if i not in seenR:
                islands += 1
                dfsRow(i)
                dfsCol(j)
        return len(points) - islands

3. 优化行列处理

上述代码有很多冗余，实际上我们对行列的搜索，没有任何本质区别。
只不过是因为同一个index，可能是行也可能是列，所以我们做了区分。
实际上，只要我们能区分行列的index，代码就可以缩减一半了。

行的index我们还可以用0～N - 1，列的index我们使用N～2N-1就可以了。

    def removeStones(self, points):
        index = collections.defaultdict(set)
        for i, j in points:
            index[i].add(j + 10000)
            index[j + 10000].add(i)

        def dfs(i):
            seen.add(i)
            for j in index[i]:
                if j not in seen:
                    dfs(j)

        seen = set()
        islands = 0
        for i, j in points:
            if i not in seen:
                islands += 1
                dfs(i)
                dfs(j + 10000)
        return len(points) - islands

4. 换个思考角度

我们之前的思路是，对石头所在point进行搜索。
有了以上代码，我们就会发现，其实我们搜索的元素是行列的index。

我们以为是行列把石头连接在了一起。
换个角度思考，也可以是一个石头把它所在行列坐标连在了一起。

我们的输入是所有的石头，每个石头都固定连接两个元素。
想到这里，union find的思路就已经呼之欲出了。

C++:

    int removeStones(vector<vector<int>>& stones) {
        for (int i = 0; i < stones.size(); ++i)
            uni(stones[i][0], ~stones[i][1]);
        return stones.size() - islands;
    }

    unordered_map<int, int> f;
    int islands = 0;

    int find(int x) {
        if (!f.count(x)) f[x] = x, islands++;
        if (x != f[x]) f[x] = find(f[x]);
        return f[x];
    }

    void uni(int x, int y) {
        x = find(x), y = find(y);
        if (x != y) f[x] = y, islands--;
    }

Java:

    Map<Integer, Integer> f = new HashMap<>();
    int islands = 0;

    public int removeStones(int[][] stones) {
        for (int i = 0; i < stones.length; ++i)
            union(stones[i][0], ~stones[i][1]);
        return stones.length - islands;
    }

    public int find(int x) {
        if (f.putIfAbsent(x, x) == null)
            islands++;
        if (x != f.get(x))
            f.put(x, find(f.get(x)));
        return f.get(x);
    }

    public void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (f.get(x) != y) {
            f.put(find(x), find(y));
            islands--;
        }
    }

Python:

    def removeStones(self, points):
        UF = {}
        def find(x):
            if x != UF[x]:
                UF[x] = find(UF[x])
            return UF[x]
        def union(x, y):
            UF.setdefault(x, x)
            UF.setdefault(y, y)
            UF[find(x)] = find(y)

        for i, j in points:
            union(i, ~j)
        return len(points) - len({find(x) for x in UF})

5. 构造移走石头方案

逆向思维，来看一下，如果开始只有一个石头，每次都只能放一个新石头在同行或同列，我们能否构造出整个岛屿。
还是不难得，可以用dfs里查找石头的顺序放，就可以构造整个岛屿了。
反之，按照反序也可以移走整个岛屿直到剩下一个石头。