发信人: athrunzara (苏奕文)

本人今年北美研一,随便在谷歌投了一波简历感受了某种意义上的世界级难度,肯定凉了。在这里发出题目望各位大佬讨论解答,让我看看各位的思路。
移石子问题:O 为石子 X为空格
例1如
X O X X X O
O X O X X X
X X X O O X
X O O X X X
O X X X X X

移除石子的规则:当石子i所在的行或者列有2个以上(包含两个)石子的时候,可以移除石子i。例如例1中左下角的石子可以被移除,原因是该石子所在的行虽然只有它一个,但是它所在的列包含两个石子。因此,左下角石子可以移除。

例2:
X O X
O X X
例2已经不能移除石子,其原因为所有石子所在的行或者列都只有他一个。

求问: 当石子不能再被移除时,该棋盘剩下的最少的石子的数量。(其实也是最多可以移除多少个石子)。
要求:设计策略,用尽量少的复杂度来解决该问题。

本人基本懵了45分钟,起初因为交流不通畅还理解错了题意,理解对了之后觉得凉透了。虽然凉了,但是还是希望得到解答的思路。望各位大佬学长学姐,学弟学妹帮助答疑解惑。靴靴


在二维平面上,我们将石头放置在一些整数坐标点上。每个坐标点上最多只能有一块石头。

现在,move 操作将会移除与网格上的某一块石头共享一列或一行的一块石头。

我们最多能执行多少次 move 操作?

 

示例 1:

输入:stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]输出:5

示例 2:

输入:stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]输出:3

示例 3:

输入:stones = [[0,0]]输出:0

 

提示:

  1. 1 <= stones.length <= 1000

  2. 0 <= stones[i][j] < 10000

  


发信人: xxpxxxxp (xxpxxxxp)

2楼正解,DSU轻松可解,DFS也行
关键就是设立一个图,任意两个在同一行/列的石子有一条路径。那么最终有几个独立的可连通图,最后就可以剩下几个石子(可证明)。


发信人: server (Server)

典型的并查集问题。
可以看看朋友圈那个问题,同类问题比这简单些,DFS、BFS、并查集都可


https://leetcode-cn.com/problems/friend-circles/solution/peng-you-quan-by-leetcode/


方法一: 深度优先搜索

思路


首先将处于同一行或同一列的石头两两相连,这样会产生一个图。在这个图里面,互相连通的石子组成一个连通分量。


显然,总有办法将一个连通分量中的石子依次移除,直到只剩下一个。首先,我们要知道每个石子都属于一个连通分量,同时在一个连通分量中移除石子不会影响到其他的连通分量。在有了这个前提之下,我们可以推断出,如果把连通分量作为一个生成树来看,每次都移除树中的叶子节点,重复这个操作,最后就只会剩下一个根节点。


算法


在这里我们用深度优先搜索来计算图中的连通分量的个数,通过深度优先搜索遍历连通分量中的每个节点。在每个连通分量里面,最多能移除石子的数量为 连通分量中石子数量 - 1。


JavaPython

class Solution {

    public int removeStones(int[][] stones) {

        int N = stones.length;


        // graph[i][0] = the length of the 'list' graph[i][1:]

        int[][] graph = new int[N][N];

        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]) {

                    graph[i][++graph[i][0]] = j;

                    graph[j][++graph[j][0]] = i;

                }


        int ans = 0;

        boolean[] seen = new boolean[N];

        for (int i = 0; i < N; ++i) if (!seen[i]) {

            Stack<Integer> stack = new Stack();

            stack.push(i);

            seen[i] = true;

            ans--;

            while (!stack.isEmpty()) {

                int node = stack.pop();

                ans++;

                for (int k = 1; k <= graph[node][0]; ++k) {

                    int nei = graph[node][k];

                    if (!seen[nei]) {

                        stack.push(nei);

                        seen[nei] = true;

                    }

                }

            }

        }


        return ans;

    }

}

复杂度分析


时间复杂度: O(N^2)O(N 

2

 ),其中 NN 是石头的数量。


空间复杂度: O(N^2)O(N 

2

 )。


方法二: 并查集

思路


在方法一中,我们通过深度优先搜索来计算隐式图中连通分量的个数。实际上有更高效的解决方法,那就是用并查集。


算法


对于一个坐标为 (i, j) 的石子来说,需要把行 i 和列 j 合并,因为并查集是一维的,用 j+10000 来代替 j。在将所有石子的行和列都合并好之后,只需数一下并查集中有几个集合就可以得到答案了。


简洁起见,这里实现的并查集就不根据 rank 来合并了。因此渐进复杂度会比用 rank 的高一点。


JavaPython

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);

    }

}

复杂度分析


时间复杂度: O(N \log N)O(NlogN),其中 NN 是 stones 的大小。(如果根据 rank 来做合并操作,时间复杂度就是 O(N * \alpha(N))O(N∗α(N)),其中 \alphaα 是 Ackerman 函数的反函数。)


空间复杂度: O(N)O(N)。