LeetCode每日一题：移除最多的同行或同列石头

传送门

思路

可以把所有在同一行和同一列的石子连起来，这样就能构成若干个连通分量。而根据题意，不难想到每一个连通分量最后都能删到只剩一颗石子，所以答案显然就是石子总数减去连通分量的个数。

用并查集来维护连通关系。

代码

第一种是最直接的O(n²)连图。

class Solution {
private:
    unordered_map<int, int> father;
    unordered_map<int, int> rank;
public:
    int cnt;
    void init(int n) {
        cnt = n;
        for(int i = 0; i < n; i++) {
            father[i] = i;
            rank[i] = 1;
        }
    }

    int find(int x) {
        return father[x] == x ? x : father[x] = find(father[x]);
    }

    void merge(int x, int y) {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty) {
            if (rank[rootx] < rank[rooty]) {
                swap(rootx, rooty);
            }
            father[rooty] = rootx;
            if (rank[rootx] == rank[rooty]) rank[rootx] += 1;
            cnt--;
        }
    }

    int removeStones(vector<vector<int>>& stones) {
        const int N = stones.size();
        init(N);

        // for(int i = 0; i < N; i++) {
        //     cout <<stones[i][0] <<" " << stones[i][1] << endl;
        // }

        for(int i = 0; i < N; i++) {
            for(int j = i + 1; j < N; j++) {
                if (stones[i][0] == stones[j][0] || 
                    stones[i][1] == stones[j][1]) {
                        // printf("%d's father is %d\n", i, j);
                        merge(i, j);
                    }
            }
        }

        return N - cnt;
    }
};

第二种是根据映射原理，直接对点的xy坐标链接，这样做的复杂度是O(n).

作者：carlsun-2

class Solution {
private:
    int n = 20005; // 根据坐标范围而定
    int father[20005];

    // 并查集初始化
    void init() {
        for (int i = 0; i < n; ++i) {
            father[i] = i;
        }
    }
    // 并查集里寻根的过程
    int find(int u) {
        return u == father[u] ? u : father[u] = find(father[u]);
    }
    // 将v->u 这条边加入并查集
    void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return ;
        father[v] = u;
    }
    // 判断 u 和 v是否找到同一个根
    bool same(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }
public:
    int removeStones(vector<vector<int>>& stones) {
        init();
        for (int i = 0; i < stones.size(); i++) join(stones[i][0], stones[i][1] + 10000);
        unordered_map<int, bool> umap;
        for (int i = 0; i < stones.size(); i++) {
            umap[find(stones[i][0])] = true;
            umap[find(stones[i][1] + 10000)] = true;
        }
        return stones.size() - umap.size();
    }
};