2021-03-10

JiayangWu · JiayangWu · commit 477c31753a57 · 2021-03-10T16:14:03.000-05:00
diff --git a/1583.统计不开心的朋友/1583-统计不开心的朋友.py b/1583.统计不开心的朋友/1583-统计不开心的朋友.py
@@ -0,0 +1,32 @@
+class Solution(object):
+    def unhappyFriends(self, n, preferences, pairs):
+        """
+        :type n: int
+        :type preferences: List[List[int]]
+        :type pairs: List[List[int]]
+        :rtype: int
+        """
+        # 建立亲密度矩阵，prefer_degrees[i][j]即为 i 对 j 的亲密度
+        prefer_degrees = [[-n-1 for _ in range(n)] for _ in range(n)]
+        for i, preference in enumerate(preferences):
+            for degree, j in enumerate(preference):
+                prefer_degrees[i][j] = -degree
+
+        # 建立配对字典，给定x， ppl2friends[x]即为 x 分配的朋友
+        ppl2friends = dict()
+        for x, y in pairs:
+            ppl2friends[x] = y
+            ppl2friends[y] = x
+
+        def isUnhappy(x):
+            # 判定 x 是否快乐
+            y = ppl2friends[x]
+
+            for u in range(n):
+                v = ppl2friends[u]
+                if x != u and prefer_degrees[x][u] > prefer_degrees[x][y] and \
+                   prefer_degrees[u][x] > prefer_degrees[u][v]:
+                   return 1
+            return 0
+
+        return sum([isUnhappy(i) for i in range(n)])
diff --git a/1584.连接所有点的最小费用/1584-连接所有点的最小费用.py b/1584.连接所有点的最小费用/1584-连接所有点的最小费用.py
@@ -0,0 +1,54 @@
+
+class UnionFindSet(object):
+    def __init__(self, n):
+        # m, n = len(grid), len(grid[0])
+        self.roots = [i for i in range(n + 1)]
+        self.rank = [0 for i in range(n + 1)]
+        self.count = n
+        
+    def find(self, member):
+        tmp = []
+        while member != self.roots[member]:
+            tmp.append(member)
+            member = self.roots[member]
+        for root in tmp:
+            self.roots[root] = member
+        return member
+        
+    def union(self, p, q):
+        parentP = self.find(p)
+        parentQ = self.find(q)
+        if parentP != parentQ:
+            if self.rank[parentP] > self.rank[parentQ]:
+                self.roots[parentQ] = parentP
+            elif self.rank[parentP] < self.rank[parentQ]:
+                self.roots[parentP] = parentQ
+            else:
+                self.roots[parentQ] = parentP
+                self.rank[parentP] -= 1
+            self.count -= 1
+
+class Solution(object):
+    def minCostConnectPoints(self, points):
+        """
+        :type points: List[List[int]]
+        :rtype: int
+        """
+        from heapq import *
+        queue = []
+        res = 0
+        n = len(points)
+        for i in range(n):
+            for j in range(i + 1, n):
+                d = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
+                heappush(queue, (d, i, j))
+
+        ufs = UnionFindSet(n)
+        while ufs.count > 1:
+            d, i, j = heappop(queue)
+
+            if ufs.find(i) != ufs.find(j):
+                res += d
+                ufs.union(i, j)
+
+        return res
