鱼C论坛

 找回密码
 立即注册
查看: 41|回复: 0

[学习笔记] Leetcode 1584. Min Cost to Connect All Points

[复制链接]
最佳答案
40 
发表于 2020-9-16 21:25:21 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
You are given an array points representing integer coordinates of some points on a 2D-plane, where points = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.



Example 1:

Screenshot from 2020-09-16 09-23-31.png

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Explanation:

Screenshot from 2020-09-16 09-23-40.png

We can connect the points as shown above to get the minimum cost of 20.
Notice that there is a unique path between every pair of points.
Example 2:

Input: points = [[3,12],[-2,5],[-4,1]]
Output: 18
Example 3:

Input: points = [[0,0],[1,1],[1,0],[-1,1]]
Output: 4
Example 4:

Input: points = [[-1000000,-1000000],[1000000,1000000]]
Output: 4000000
Example 5:

Input: points = [[0,0]]
Output: 0


Constraints:

1 <= points.length <= 1000
-106 <= xi, yi <= 106
All pairs (xi, yi) are distinct.

  1. class UnionFind:
  2.     def __init__(self, n: int):
  3.         self.parent = list(range(n))
  4.         self.size = [1] * n
  5.         
  6.     def find(self, x):
  7.         if self.parent[x] != x:
  8.             self.parent[x] = self.find(self.parent[x])
  9.         return self.parent[x]
  10.    
  11.     def union(self, x, y):
  12.         rx, ry = self.find(x), self.find(y)
  13.         if rx == ry: return False
  14.         
  15.         if self.size[rx] < self.size[ry]:
  16.             rx, ry = ry, rx
  17.             
  18.         self.parent[ry] = rx
  19.         self.size[rx] += self.size[ry]
  20.         
  21.         return True
  22.         
  23. class Solution:
  24.     def minCostConnectPoints(self, points: List[List[int]]) -> int:
  25.         N = len(points)
  26.         edges = []
  27.         res = 0
  28.         
  29.         for i in range(N):
  30.             for j in range(i + 1, N):
  31.                 distance = abs(points[i][0] - points[j][0])
  32.                 distance += abs(points[i][1] - points[j][1])
  33.                
  34.                 edges.append((distance, i, j))
  35.         
  36.         edges.sort()
  37.         
  38.         unionfind = UnionFind(N)
  39.         
  40.         for edge in edges:
  41.             dis, i, j = edge
  42.             if unionfind.union(i, j):
  43.                 res += dis
  44.             
  45.         return res
复制代码

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1

GMT+8, 2020-9-28 02:00

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表