[LeetCode] 947. Most Stones Removed with Same Row or Column

[grandyang]

On a 2D plane, we place stones at some integer coordinate points.  Each coordinate point may have at most one stone.

Now, a  move  consists of removing a stone that shares a column or row with another stone on the grid.

What is the largest possible number of moves we can make?

Example 1:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5

Example 2:

Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3

Example 3:

Input: stones = [[0,0]]
Output: 0

Note:

1. 1 <= stones.length <= 1000
2. 0 <= stones[i][j] < 10000

这道题给了我们一堆石子坐标，说是每次可以移除一个石子，但是条件是必须有其他的一个石子跟这个石子共行或者共列，问最多可以移除多少个石子。从例子1来看，必须要按照一个特定的顺序来移除石子，才能够移除5个，若是随机移除的话，可能会少于5个。而如果有两个石子，各自分别不共行不共列，那么无论如何都无法移除石子，所以说只有属于一个群组的石子才可以移除。这里定义的属于同一的群组的方法是共行或共列，跟 Number of Islands 中的定义有些区别，那道题是所有相连的1当作一个岛屿，这里把相邻的条件换成共行或共列即可。而对于属于同一个群组的石子，总有办法能按顺序移除到只剩一个石子，所以总共有多少个群组，最终就会剩下多少个石子，最大的移除个数就是总石子个数减去群组个数。现在问题就变成了找不同群组的个数，博主最先想的利用和 Number of Islands 中一样的方法，但不幸的是不论 DFS 还是 BFS 的方法都超时了，可能是由于不知道整个二维数组的范围大小，所以记录访问过的结点只能保存横纵坐标，不能 encode 成一个数字，从而超时了。为了能通过 OJ，必须要进行一些优化，由于这里关心的是同一行或者同一列上的结点，可以用两个 HashMap，其中 rowMap 建立每个横坐标和该行上所有出现的石子的纵坐标组成的数组之间的映射，同理，colMap 建立每个纵坐标和该列上所有出现的石子的横坐标组成数组之间的映射。然后遍历 rowMap，对于其中每个横坐标调用递归函数，这个递归函数是计算群组中所有结点的个数，因为同一行上的所有结点必定都是属于同一个群组的，所以可以一起计算。现在是为了找出跟该行上所有的石子共列的其他石子。通过 rowMap 可以找出所有和 row 共行的石子，对于每个石子，可以通过 colMap 找出跟其共列的石子，然后再次调用递归即可。找出了整个群组的个数，要移除的个数就是总个数减去1，将这个值加到结果 res 上。注意这里使用了个 trick，和0比较，取较大值。因为可能会遍历到之前计算过的结点，此时递归函数直接返回了0，减去1后变为 -1，为了不减少 res 的值，要和0比较并取较大值，参见代码如下：

解法一：

class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        unordered_map<int, vector<int>> rowMap, colMap;
        unordered_set<int> rowVisited;
        int res = 0;
        for (auto stone : stones) {
            rowMap[stone[0]].push_back(stone[1]);
            colMap[stone[1]].push_back(stone[0]);
        }
        for (auto a : rowMap) {
            res += max(0, helper(rowMap, colMap, a.first, rowVisited) - 1);
        }
        return res;
    }
    int helper(unordered_map<int, vector<int>>& rowMap, unordered_map<int, vector<int>>& colMap, int row, unordered_set<int>& rowVisited) {
        if (rowVisited.count(row)) return 0;
        rowVisited.insert(row);
        int res = rowMap[row].size();
        for (int c : rowMap[row]) {
            for (int r : colMap[c]) {
                res += helper(rowMap, colMap, r, rowVisited);
            }
        }
        return res;
    }
};

对于这种求群组个数的题目，还有一大神器就是联合查找 Union Find 的方法，在很多题目中都使用了，比如 Number of Islands II。一般来说，UF 算法的思路是每个个体先初始化为不同的群组，然后遍历有关联的两个个体，如果发现其 getRoot 函数的返回值不同，则手动将二者加入一个群组，然后总群组数自减1。这里就要分别说一下 root 数组，和 getRoot 函数。两个同群组的个体，通过 getRoot 函数一定会返回相同的值，但是其在 root 数组中的值不一定相同，可以类比成 getRoot 函数返回的是祖先，如果两个人的祖先相同，那么其是属于一个家族的（这里不是指人类共同的祖先哈）。root 可以用数组或者 HashMap 来表示，如果个体是数字的话，那么数组就 OK，如果个体是字符串的话，可能就需要用 HashMap 了。root 数组的初始化可以有两种，可以均初始化为 -1，或者都初始化为不同的数字，博主一般喜欢初始化为不同的数字。getRoot 函数的写法也可用递归或者迭代的方式，可参见博主之前的帖子 Redundant Connection II 中的讨论部分。这里的话将每个石子都先当作是一个群组，这样就初始化了n个群组，分别在 root 数组中进行初始化，然后遍历任意两个石子组合，若这两个石子的横纵坐标有一个相同的话，说明是同一个群组的，将二者关联上，关联之前要分别对其调用一次 getRoot 函数，以便找到其最终的祖先结点。更新结束了之后就要数最终还剩几个群组了，将 root 数组遍历一遍，当某个结点还是初始值时，说明其是一个群组的祖先结点，计数器 cnt 自增1，最终的结果就返回 n-cnt 即可，参见代码如下：

解法二：

class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        int cnt = 0, n = stones.size();
        vector<int> root(n);
        for (int i = 0; i < n; ++i) root[i] = i;
        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]) {
                    root[getRoot(root, i)] = getRoot(root, j);
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            if (root[i] == i) ++cnt;
        }
        return n - cnt;
    }
    int getRoot(vector<int>& root, int x) {
        return x == root[x] ? x : getRoot(root, root[x]);
    }
};

Github 同步地址:

#947

参考资料：

https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/

https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/discuss/197851/C%2B%2B-DFS

https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/discuss/217790/C%2B%2B-union-find

https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/discuss/197668/Count-the-Number-of-Islands-O(N)

LeetCode All in One 题目讲解汇总(持续更新中...)