Updates

wuduhren · wuduhren · commit 758ba68d95d7 · 2022-08-25T08:36:37.000+02:00
diff --git a/problems/python3/design-twitter.py b/problems/python3/design-twitter.py
@@ -0,0 +1,49 @@
+class Twitter:
+
+    def __init__(self):
+        self.followData = collections.defaultdict(set)
+        self.tweetData = collections.defaultdict(list)
+        self.count = 0
+        
+
+    def postTweet(self, userId: int, tweetId: int) -> None:
+        self.tweetData[userId].append((self.count, tweetId))
+        self.count -= 1
+
+    
+    def getNewsFeed(self, userId: int) -> List[int]:
+        newsFeed = []
+        h = []
+        
+        self.followData[userId].add(userId)
+        for followeeId in self.followData[userId]:
+            if followeeId not in self.tweetData: continue
+            index = len(self.tweetData[followeeId])-1
+            count, tweetId = self.tweetData[followeeId][index]
+            h.append((count, tweetId, followeeId, index-1))
+        heapq.heapify(h)
+        
+        while h and len(newsFeed)<10:
+            _, tweetId, userId, index = heapq.heappop(h)
+            newsFeed.append(tweetId)
+            if index>=0:
+                count, tweetId2 = self.tweetData[userId][index]
+                heapq.heappush(h, (count, tweetId2, userId, index-1))
+        return newsFeed
+        
+        
+
+    def follow(self, followerId: int, followeeId: int) -> None:
+        self.followData[followerId].add(followeeId)
+
+    def unfollow(self, followerId: int, followeeId: int) -> None:
+        if followerId not in self.followData: return
+        self.followData[followerId].remove(followeeId)
+
+
+# Your Twitter object will be instantiated and called as such:
+# obj = Twitter()
+# obj.postTweet(userId,tweetId)
+# param_2 = obj.getNewsFeed(userId)
+# obj.follow(followerId,followeeId)
+# obj.unfollow(followerId,followeeId)
diff --git a/problems/python3/find-median-from-data-stream.py b/problems/python3/find-median-from-data-stream.py
@@ -0,0 +1,32 @@
+class MedianFinder:
+
+    def __init__(self):
+        self.large = [] #store nums larger or equal to the median
+        self.small = [] #store nums samaller to the median
+
+    def addNum(self, num: int) -> None:
+        if not self.large and not self.small:
+            heapq.heappush(self.large, num)
+        elif num>=self.findMedian():
+            heapq.heappush(self.large, num)
+            self.balance()
+        else:
+            heapq.heappush(self.small, -num)
+            self.balance()
+    
+    def balance(self) -> None:
+        #make the length of two heaps as even as posible
+        if len(self.large)>len(self.small)+1:
+            num = heapq.heappop(self.large)
+            heapq.heappush(self.small, -num)
+        
+        if len(self.small)>len(self.large):
+            num = -heapq.heappop(self.small)
+            heapq.heappush(self.large, num)
+    
+
+    def findMedian(self) -> float:
+        if (len(self.large)+len(self.small))%2==0:
+            return (self.large[0]-self.small[0])/2
+        else:
+            return self.large[0]
diff --git a/problems/python3/k-closest-points-to-origin.py b/problems/python3/k-closest-points-to-origin.py
@@ -0,0 +1,10 @@
+class Solution:
+    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
+        h = []
+        
+        for x, y in points:
+            dis = (x**2+y**2)**0.5
+            heapq.heappush(h, (-dis, x, y))
+            if len(h)>k: heapq.heappop(h)
+        
+        return [(x, y) for dis, x, y in h]
diff --git a/problems/python3/task-scheduler.py b/problems/python3/task-scheduler.py
@@ -0,0 +1,23 @@
+class Solution:
+    def leastInterval(self, tasks: List[str], n: int) -> int:
+        q = collections.deque()
+        h = []
+        time = 0
+        
+        counter = collections.Counter(tasks)
+        for task in counter:
+            heapq.heappush(h, (-counter[task], task))
+        
+        while h or q:
+            if q and q[0][0]<=time:
+                _, count, task = q.popleft()
+                heapq.heappush(h, (-count, task))
+            
+            if h:
+                count, task = heapq.heappop(h)
+                count*=-1
+                count -= 1
+                if count>0: q.append((time+n+1, count, task))
+            time += 1
+        
+        return time
