Skip to content

Latest commit

 

History

History
269 lines (204 loc) · 10.3 KB

947.most-stones-removed-with-same-row-or-column.md

File metadata and controls

269 lines (204 loc) · 10.3 KB

题目地址 (947. 移除最多的同行或同列石头)

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

题目描述

n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。

如果一块石头的 同行或者同列 上有其他石头存在,那么就可以移除这块石头。

给你一个长度为 n 的数组 stones ,其中 stones[i] = [xi, yi] 表示第 i 块石头的位置,返回 可以移除的石子 的最大数量。

 

示例 1:

输入:stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
输出:5
解释:一种移除 5 块石头的方法如下所示:
1. 移除石头 [2,2] ,因为它和 [2,1] 同行。
2. 移除石头 [2,1] ,因为它和 [0,1] 同列。
3. 移除石头 [1,2] ,因为它和 [1,0] 同行。
4. 移除石头 [1,0] ,因为它和 [0,0] 同列。
5. 移除石头 [0,1] ,因为它和 [0,0] 同行。
石头 [0,0] 不能移除,因为它没有与另一块石头同行/列。
示例 2:

输入:stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
输出:3
解释:一种移除 3 块石头的方法如下所示:
1. 移除石头 [2,2] ,因为它和 [2,0] 同行。
2. 移除石头 [2,0] ,因为它和 [0,0] 同列。
3. 移除石头 [0,2] ,因为它和 [0,0] 同行。
石头 [0,0] 和 [1,1] 不能移除,因为它们没有与另一块石头同行/列。
示例 3:

输入:stones = [[0,0]]
输出:0
解释:[0,0] 是平面上唯一一块石头,所以不可以移除它。
 

提示:

1 <= stones.length <= 1000
0 <= xi, yi <= 104
不会有两块石头放在同一个坐标点上

前置知识

思路

读完题目之后, 看了下数据范围。我猜测可能和动态规划什么的有关,而且时间复杂度是 $O(n^2)$ 左右,其中 n 为 stones 的长度。继续看了下示例,然后跟着思考了一下,发现很像是某种联通关系。 类似的题目有很多,题目描述记不太清楚了。大概意思是给你一个二维网格,行和列需要一起增加,求最小和什么的。这类题目都是行和列具有某种绑定关系。 于是我想到了使用并查集来做。 后面想了一下,反正就是求联通区域的个数,因此使用 DFS 和 BFS 都可以。如果你想使用 DFS 或者 BFS 来解,可以结合我之前写的 小岛专题 练习一下哦。

继续分析下题目。 题目的意思是任意一个石头可以消除和它同行和同列的其他石子。于是我就想象出了下面这样一幅图,其中红色的方块表示石子,方块的连线表示离得最近的可以消除的石子。实际上,一个石子除了可以消除图中线条直接相连的石子,还可以消除邻居的邻居。这提示我们使用并查集维护这种联通关系,联通的依据自然就是列或者行一样。

上面是一个全联通的图。如下是有两个联通域的图。

有了上面的知识,其实就可以将石子全部建立并查集的联系,并计算联通子图的个数。答案就是 n - 联通子图的个数,其中 n 为 stones 的长度。

核心代码:

n = len(stones)
# 标准并查集模板
uf = UF(n)
# 两个 for 循环作用是将所有石子两两合并
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]: uf.union(i, j)
return n - uf.cnt

有的人想问,这可行么?即我可以将一个联通子图的石子移除只剩下一个么?

答案是肯定的。其实上面我提到了这道题也可使用 DFS 和 BFS 的方式来做。如果你使用 DFS 的方式来做,会发现其实 DFS 路径的取反就是消除的顺序,当然消除的顺序不唯一,因为遍历访问联通子图的序列并不唯一。 如果题目要求我们求移除顺序,那我们可以考虑使用 DFS 来做,同时记录路径信息即可。

使用遍历的方式(BFS 或者 DFS),由于每次访问一个石子都需要使用 visited 来记录访问信息防止环的产生,因此 visited 的逆序也是一个可行的移除顺序。不过这要求你的 visited 的是有序的。实现的方法有很多,有点偏题了,这里就不赘述了。

实际上,上面的并查集代码仍然可以优化。上面的思路是直接将点作为并查集的联通条件。实际上,我们可以将点的横纵坐标分别作为联通条件。即如果横坐标相同的联通到一个子图,纵坐标相同的联通到一个子图。如下图:

为了达到这个模板,我们不能再初始化的时候计算联通域数量了,即不能像上面那样 uf = UF(n)(此时联通域个数为 n)。因为横坐标,纵坐标分别有多少不重复的我们是不知道的,一种思路是先计算出横坐标,纵坐标分别有多少不重复的。这当然可以,还有一种思路是在 find 过程中计算,这样 one pass 即可完成,具体见下方代码区。

由于我们需要区分横纵坐标(上面图也可以看出来),因此可用一种映射区分二者。由于题目限定了横纵坐标取值为 10000 以内(包含 10000),一种思路就是将 x 或者 y 加上 10001。

核心代码:

n = len(stones)
uf = UF(0)
for i in range(n):
    uf.union(stones[i][0] + 10001, stones[i][1])
return n - uf.cnt

代码

并查集

代码支持: Python3

其中 class UF 部分是标准的无权并查集模板,我一行代码都没变。关于模板可以去 并查集 查看。

class UF:
    def __init__(self, M):
        self.parent = {}
        self.cnt = 0
        # 初始化 parent,size 和 cnt
        for i in range(M):
            self.parent[i] = i
            self.cnt += 1

    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
        return x
    def union(self, p, q):
        if self.connected(p, q): return
        leader_p = self.find(p)
        leader_q = self.find(q)
        self.parent[leader_p] = leader_q
        self.cnt -= 1
    def connected(self, p, q):
        return self.find(p) == self.find(q)

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        n = len(stones)
        uf = UF(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]: uf.union(i, j)
        return n - uf.cnt

复杂度分析

令 n 为数组 stones 的长度。

  • 时间复杂度:$O(n^2logn)$
  • 空间复杂度:$O(n)$

优化的并查集

代码支持: Python3

class UF:
    def __init__(self, M):
        self.parent = {}
        self.cnt = 0

    def find(self, x):
        if x not in self.parent:
            self.cnt += 1
            self.parent[x] = x
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
        return x
    def union(self, p, q):
        if self.connected(p, q): return
        leader_p = self.find(p)
        leader_q = self.find(q)
        self.parent[leader_p] = leader_q
        self.cnt -= 1
    def connected(self, p, q):
        return self.find(p) == self.find(q)

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        n = len(stones)
        uf = UF(0)
        for i in range(n):
            uf.union(stones[i][0] + 10001, stones[i][1])
        return n - uf.cnt

复杂度分析

令 n 为数组 stones 的长度。

  • 时间复杂度:$O(nlogn)$
  • 空间复杂度:$O(n)$

DFS

代码支持: Java

by 一位不愿透露姓名的热心网友。

public int removeStones(int[][] stones) {
        Set visit = new HashSet();
        int count = 0;
        int offset = 10000;
        HashMap <Integer,List<int []>>map = new HashMap();

        // 构造图 每一项是一个节点
        for (int i = 0; i < stones.length; i++) {
            int [] node = stones[i];
            List<int []> list =   map.getOrDefault(node[0]-offset,new ArrayList<>());
            list.add(node);
            map.put(node[0]-offset,list);

            List<int []> list1 = map.getOrDefault(node[1],new ArrayList<>());
            list1.add(node);
            map.put(node[1],list1);
        }
        // 寻找联通分量
        for (int i = 0; i < stones.length; i++) {
            int [] node = stones[i];
            if (!visit.contains((node))){
                visit.add((node));
                dfs(node,visit,map);
                count++;
            }
        }
        return stones.length-count;
    }

    // 遍历节点
    public void dfs(int[]node, Set set,HashMap <Integer,List<int []>>map){
        int offset = 10000;
        List<int []> list =   map.getOrDefault(node[0]-offset,new ArrayList<>());
        for (int i = 0; i < list.size(); i++) {
            int[] item = list.get(i);
            if (!set.contains((item))){
                set.add((item));
                dfs(item,set,map);
            }
        }
        List<int []> list2 =   map.getOrDefault(node[1],new ArrayList<>());
        for (int i = 0; i < list2.size(); i++) {
            int[] item = list2.get(i);
            if (!set.contains((item))){
                set.add((item));
                dfs(item,set,map);
            }
        }
    }

复杂度分析

令 n 为数组 stones 的长度。

  • 时间复杂度:建图和遍历图的时间均为 $O(n)$
  • 空间复杂度:$O(n)$

力扣的小伙伴的点下我头像的关注按钮,这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 38K star 啦。