Re: [閒聊] 每日LeetCode

看板Marginalman作者Rushia (みけねこ的鼻屎)時間3年前 (2022/11/14 10:51)推噓3(3推 0噓 2→)

留言5則, 5人參與討論串101/719 (看更多)

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： ---------------------------------- class Solution { private int[] parent = new int[20001]; private int islands = 0; public int removeStones(int[][] stones) { for (int[] stone : stones) { union(stone[1], stone[0] + 10000); } return stones.length - islands; } public int find(int x) { if (parent[x] == 0) { islands++; parent[x] = x; } return parent[x] == x ? x : (parent[x] = find(parent[x])); } public void union(int x, int y) { x = find(x); y = find(y); if (x != y) { parent[x] = y; islands--; } } } ---------------------------------- 一開始是用DFS@@ -- https://i.imgur.com/bFRiqA3.jpg