Re: [閒聊] 每日LeetCode

作者: Rushia (みけねこ的鼻屎)   2023-09-16 02:44:10
https://leetcode.com/problems/min-cost-to-connect-all-points/description/
1584. Min Cost to Connect All Points
給你一個陣列表示 n 個點 points[i] = [xi, yi],連結點 i 和點 j 的成本為:
|xi - xj| + |yi - yj| ,返回可以連結所有的點的最小成本,且滿足任意兩點之間
只能有一條簡單路徑(不可有迴圈)
思路:
1.先找出所有的邊的長度,並把這些邊的起點、終點、長度保存起來依照長度排序。
(這邊用heap)
2.我們每次都從邊集合裡面拿出最小的邊,然後判斷兩個頂點是否是同一個起點,
如果是的話跳過,如果不是的話把兩個集合合併,這個過程也要更新集合的相關資訊
,像是成本、集合大小等等。
(這邊用併查集)
3.如果在上面步驟的過程中發現某個集合的點數量等於題目要求的就直接返回。
Java Code:

Links booklink

Contact Us: admin [ a t ] ucptt.com