@ninijia 在 Leetcode每日一题练习 ------ 947. 移除最多的同行或同列石头 中发帖
从Leetcode 每日一题练习继续讨论:
947. 移除最多的同行或同列石头
947. Most Stones Removed with Same Row or Column
题解
本题通过观察可以发现只要彼此之间有关联(共行或共列)的一系列坐标, 最后仅保留一个, 其余均可通过某种顺序被全部删除. 如(0,0), (0,2), (2,0), (2,2), 四个点之前每个都和另外一个有关联, 则最终四个点仅保留一个. 也就意味着, 如果a与b有关联, 则a b可视为在同一个集合中, 若c和a有关联, 则c b a可视为在同一个集合中, 以此类推, 直到没有新的数字加入这个集合, 这里可以使用并查集, 最后只需用全部坐标点的个数减掉集合的个数即得到可以被删除点的最多个数.
问题在于, 如何构造并查集, 由题目可知, 处在同一行或者同一列的点均可以视为在同一个集合中, 则可以将同一行...