【LeetCode】947. Most Stones Removed with Same Row or Column 解题报告（Python & C++）

作者：负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/

题目描述

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 <= stones.length <= 1000
0 <= stones[i][j] < 10000

题目大意

在二维坐标的整数坐标点上，有一些石头，如果一个石头和另外一个石头的横坐标或者纵坐标相等，那么认为他们是有链接的。我们每次取一个和别人有链接的石头，问最终能取得多少个石头。

解题方法

并查集

这个题翻译一下就是，横或者纵坐标相等的坐标点会互相链接构成一个区域，问总的有多少个独立的区域。结果是总的石头数减去独立区域数。

所以，我们根本不用考虑太多，只需要统计有多少区域即可。这个方法最简单的就是并查集。

思路是，两重循环，分别判断石头两两之间是否有链接，如果有链接，那么把他们组成同一个区域。这样的优点是我们只需要和石头等长的数组放每个的parent即可。最后统计最后的区域中-1的数量就是独立区域的个数。石头个数减去独立区域数即可。

python代码如下，可惜超时了。

class Solution(object):

    def removeStones(self, stones):

        """

        :type stones: List[List[int]]

        :rtype: int

        """

        N = len(stones)

        self.map = [-1] * N

        for i in range(N):

            for j in range(i + 1, N):

                if stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]:

                    self.union(i, j)

        res = N

        print(self.map)

        for i in range(N):

            if self.map[i] == -1:

                res -= 1

        return res

    def find(self, x):

        return x if self.map[x] == -1 else self.find(self.map[x])

    def union(self, x, y):

        fx = self.find(x)

        fy = self.find(y)

        if fx != fy:

            self.map[fx] = fy

这个版本的C++可以做通过，说明了C++速度的优越性。

class Solution {

public:

    int removeStones(vector<vector<int>>& stones) {

        if(stones.size() <= 1) return 0;

        int N = stones.size();

        vector<int> p(N, -1);

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

                    u(p, i, j);

                }

            }

        }

        int res = N;

        for(auto e: p) if(e == -1) --res;

        return res;

    }

private:

    int f(vector<int> &p, int x){

        if(p[x] == -1) return x;

        return f(p, p[x]);

    }

    void u(vector<int> &p, int x, int y){

        int px = f(p, x);

        int py = f(p, y);

        if(px != py){

            p[px] = py;

        }

    }

};

其实上面这个版本可以做优化，我们不用对石头进行两两判断，而是对他们的横纵坐标同等看待。怎么区分横纵坐标呢？使用的方法是把纵坐标+10000，这样行的索引没变，纵坐标的范围跑到了后面去了。

这个做法的思路是，一个坐标其实就是把横纵坐标对应的两个区域进行了链接。所以，只需要对stones进行一次遍历把对应的区域链接到一起即可。在完成链接之后，我们最后统计一下有多少个独立的区域，需要使用set+find。

Python代码如下：

class Solution(object):

    def removeStones(self, stones):

        """

        :type stones: List[List[int]]

        :rtype: int

        """

        N = len(stones)

        self.map = [-1] * 20000

        for x, y in stones:

            self.union(x, y + 10000)

        count = set()

        return N - len({self.find(x) for x, y in stones})

    def find(self, x):

        return x if self.map[x] == -1 else self.find(self.map[x])

    def union(self, x, y):

        fx = self.find(x)

        fy = self.find(y)

        if fx != fy:

            self.map[fx] = fy

C++代码如下：

class Solution {

public:

    int removeStones(vector<vector<int>>& stones) {

        if(stones.size() <= 1) return 0;

        int N = stones.size();

        vector<int> p(20000, -1);

        for(auto stone : stones){

            u(p, stone[0], stone[1] + 10000);

        }

        set<int> parents;

        for(auto stone : stones){

            parents.insert(f(p, stone[0]));

        }

        return N - parents.size();

    }

private:

    int f(vector<int> &p, int x){

        if(p[x] == -1) return x;

        return f(p, p[x]);

    }

    void u(vector<int> &p, int x, int y){

        int px = f(p, x);

        int py = f(p, y);

        if(px != py){

            p[px] = py;

        }

    }

};

日期

2018 年 11 月 24 日 —— 周日开始！一周就过去了～

巴特西

【LeetCode】947. Most Stones Removed with Same Row or Column 解题报告（Python & C++）

目录

题目描述

题目大意

解题方法

并查集

日期

最新文章

热门文章