355. 设计推特

Difficulty
Medium
Tags
链表
URL
https://leetcode-cn.com/problems/design-twitter/
Star
设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近 10 条推文。
实现 Twitter 类：
  • Twitter() 初始化简易版推特对象
  • void postTweet(int userId, int tweetId) 根据给定的 tweetId 和 userId 创建一条新推文。每次调用此函数都会使用一个不同的 tweetId 。
  • List<Integer> getNewsFeed(int userId) 检索当前用户新闻推送中最近 10 条推文的 ID 。新闻推送中的每一项都必须是由用户关注的人或者是用户自己发布的推文。推文必须 按照时间顺序由最近到最远排序 。
  • void follow(int followerId, int followeeId) ID 为 followerId 的用户开始关注 ID 为 followeeId 的用户。
  • void unfollow(int followerId, int followeeId) ID 为 followerId 的用户不再关注 ID 为 followeeId 的用户。
示例：
输入
["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"]
[[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]
输出
[null, null, [5], null, null, [6, 5], null, [5]]

解释
Twitter twitter = new Twitter();
twitter.postTweet(1, 5); // 用户 1 发送了一条新推文 (用户 id = 1, 推文 id = 5)
twitter.getNewsFeed(1);  // 用户 1 的获取推文应当返回一个列表，其中包含一个 id 为 5 的推文
twitter.follow(1, 2);    // 用户 1 关注了用户 2
twitter.postTweet(2, 6); // 用户 2 发送了一个新推文 (推文 id = 6)
twitter.getNewsFeed(1);  // 用户 1 的获取推文应当返回一个列表，其中包含两个推文，id 分别为 -> [6, 5] 。推文 id 6 应当在推文 id 5 之前，因为它是在 5 之后发送的
twitter.unfollow(1, 2);  // 用户 1 取消关注了用户 2
twitter.getNewsFeed(1);  // 用户 1 获取推文应当返回一个列表，其中包含一个 id 为 5 的推文。因为用户 1 已经不再关注用户 2
提示：
  • 1 <= userId, followerId, followeeId <= 500
  • 0 <= tweetId <= 104
  • 所有推特的 ID 都互不相同
  • postTweet、getNewsFeed、follow 和 unfollow 方法最多调用 3 * 104 次
通过次数33,207提交次数81,081

暴力法

思路
用一个字典 来维护用户的关注列表。然后将推文按照顺序保存起来。
推送的时候直接遍历保存的链表，因为保存的时候就是有序的，所以直接遍历即可。！
题解
class Twitter:

    def __init__(self):
        self.user_follower_id = defaultdict(list)
        self.tweet_id = []


    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweet_id.append([userId, tweetId])


    def getNewsFeed(self, userId: int) -> List[int]:
        # print(self.tweet_id)
        res = []
        for u, t in self.tweet_id[::-1]:
            if u in self.user_follower_id[userId] or u == userId:
                res.append(t)
                if len(res) >= 10:
                    return res

        return res
            
    def follow(self, followerId: int, followeeId: int) -> None:
        self.user_follower_id[followerId].append(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        if followeeId in self.user_follower_id[followerId]:
            self.user_follower_id[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)

多路归并

思路
当推文特别多的时候，显然保存到一个list中不太好，所以为每一个用户开辟一个链表。
然后推送的时候，先将该用户及关注用户的头放到堆中，然后每次取出一个，再放进去一个。拿出10个的时候就结束。
题解
class Node:
    def __init__(self, key, val):
        """key 表示时间
        """
        self.key = key
        self.val = val
        self.next = None
        
class Twitter:

    def __init__(self):
        self.idx = 0
        self.user2user = defaultdict(set)
        self.user2tweet = {}
        

    def postTweet(self, userId: int, tweetId: int) -> None:
        if userId not in self.user2tweet:
            head = Node(self.idx, tweetId)
            self.idx -= 1
            self.user2tweet[userId] = head
        else:
            new_head = Node(self.idx, tweetId)
            self.idx -= 1
            new_head.next = self.user2tweet[userId]
            self.user2tweet[userId] = new_head

            
    def getNewsFeed(self, userId: int) -> List[int]:
        h = heap()
        if userId in self.user2tweet:
            h.push(self.user2tweet[userId])
        for user in self.user2user[userId]:
            if user in self.user2tweet:
                t = self.user2tweet[user]
                h.push(t)
        # print(h.print())

        res = []
        while len(h.arrs) > 0:
            temp = h.pop()
            res.append(temp.val)
            if len(res) >= 10:
                return res
            if temp.next: 
                h.push(temp.next)

        return res
            

    def follow(self, followerId: int, followeeId: int) -> None:
        if followeeId != followerId:
            self.user2user[followerId].add(followeeId)


    def unfollow(self, followerId: int, followeeId: int) -> None:
        if followeeId in self.user2user[followerId]:
            self.user2user[followerId].remove(followeeId)


class heap:
    def __init__(self):
        self.arrs = []
    
    def up(self, idx):
        if idx <= 0:
            return
        if self.arrs[(idx-1) // 2].key > self.arrs[idx].key:
            self.arrs[(idx-1)//2], self.arrs[idx] = self.arrs[idx], self.arrs[(idx-1)//2]
            self.up((idx-1)//2)
        
    def down(self, idx):
        min_idx = idx
        if idx * 2 + 1 < len(self.arrs) and self.arrs[idx * 2 + 1].key < self.arrs[min_idx].key:
            min_idx = idx * 2 + 1
        if idx * 2 + 2 < len(self.arrs) and self.arrs[idx * 2 + 2].key < self.arrs[min_idx].key:
            min_idx = idx * 2 + 2

        if min_idx != idx:
            self.arrs[min_idx], self.arrs[idx] = self.arrs[idx], self.arrs[min_idx]
            self.down(min_idx)
        

    def pop(self, idx=0):
        res = self.arrs[idx]
        self.arrs[idx] =  self.arrs[-1]
        self.arrs.pop()
        self.down(idx)
        return res

    def push(self, node):
        self.arrs.append(node)
        self.up(len(self.arrs)-1)

    def  print(self):
        temp = []
        for n in self.arrs:
            temp.append([n.key, n.val])

        return temp        

# 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)