Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2022-11-14 10:51:29
947. Most Stones Removed with Same Row or Column
给予你一个阵列表示在2D空间里面放置石头的座标,若一个石头的上下左右存在一个
石头(重叠)我们可以把该石头移除,求出最多可以移除多少个石头。
Example:
Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
Explanation:
* *
* *
* *
One way to remove 5 stones is as follows:
1. Remove stone [2,2] because it shares the same row as [2,1].
* *
* *
*
2. Remove stone [2,1] because it shares the same column as [0,1].
* *
* *
3. Remove stone [1,2] because it shares the same row as [1,0].
* *
*
4. Remove stone [1,0] because it shares the same column as [0,0].
* *
5. Remove stone [0,1] because it shares the same row as [0,0].
*
Stone [0,0] cannot be removed since it does not share a row/column with
another stone still on the plane.
Constraints:
* 1 <= stones.length <= 1000
* 0 <= xi, yi <= 10000
* No two stones are at the same coordinate point.
思路:
1.若一个石头可以被移除那么他的上下左右必包含其他石头,我们可以把所有重叠的
石头加入到一起分成好几组,这样一来只要把每一组的石头都移除直到剩下一个就
是最小的剩余石头数,而总石头数减去最小剩余石头数就是最大可拿石头数。
2.分组问题可以使用并查集,列或行有重叠的石头都是同一组,因为测资的x或y不超过
10000所以最多会有20000个集合,令parent大小为20001。
3.find的时候如果parent是0表示走访的是新的点所以islands+1(独立的新集合)
4.union的时候如果要被合并的x和y不同,则令x的parent是y,并且islands减一
(少一个独立集合)
5.返回总石头数量减去独立集合数量
JavaCode:
作者: pandix (面包屌)   2022-11-14 10:55:00
大师
作者: twosheep0603 (两羊)   2022-11-14 11:00:00
我只会用DFS 哭了
作者: TNPSCG (TNP)   2022-11-14 11:04:00
我以为重叠是紧邻才算 同行列就算喔
楼主: Rushia (みけねこ的鼻屎)   2022-11-14 11:06:00
对ㄚ 同行同列就算

Links booklink

Contact Us: admin [ a t ] ucptt.com