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