355. 设计推特 -- 合并k个有序链表的应用

355. 设计推特

合并k个有序链表的应用

# 模拟时间戳
timestamp = 0
import heapq

class Twitter:
    """
    355. 设计推特
    https://leetcode.cn/problems/design-twitter/description/
    """
    def __init__(self):
        """初始化，创建一个字典，用于userId和user对象的映射"""
        self.userMap = {}

    def postTweet(self, userId: int, tweetId: int) -> None:
        """用户userId发表一条tweet"""
        if userId not in self.userMap:
            self.userMap[userId] = self.User(userId)
        u = self.userMap[userId]
        u.post(tweetId)

    def getNewsFeed(self, userId: int) -> List[int]:
        res = []
        if userId not in self.userMap:  # 如果不存在 userId 则返回空结果列表
            return res
        users = self.userMap[userId].followed
        # 用最大堆存储所有关注列表的 Tweet，时间复杂度 logN
        pq = []
        for id in users:
            twt = self.userMap[id].head
            if twt:
                # 将time取相反数作为堆的排序值，使其成为最大堆
                heapq.heappush(pq, (-twt.time, twt))

        # 检查队列中是否有Tweet的时间最晚或已经取到10个Tweet的时候退出
        while pq and len(res) < 10:
            _, twt = heapq.heappop(pq)
            res.append(twt.id)
            if twt.next:
                # 将一个用户发布的下一个Tweet放入最大堆中对其排序
                heapq.heappush(pq, (-twt.next.time, twt.next))

        return res

    def follow(self, followerId: int, followeeId: int) -> None:
        """用户followerId关注用户followeeId"""
        if followerId not in self.userMap:
            u = Twitter.User(followerId)
            self.userMap[followerId] = u

        if followeeId not in self.userMap:
            u = Twitter.User(followeeId)
            self.userMap[followeeId] = u

        self.userMap[followerId].follow(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        """用户followerId取消关注用户followeeId"""
        if followerId in self.userMap:
            flwer = self.userMap[followerId]
            flwer.unfollow(followeeId)

    class Tweet:
        def __init__(self, id: int, time: int):
            # 需要传入推文内容（id）和发文时间
            self.id = id
            self.time = time
            self.next = None

    class User:
        # 用户类，包含用户关注的人、推文的链表头结点、用户 ID
        def __init__(self, userId: int):
            self.id = userId
            self.followed = set()  # 用户关注的人
            self.head = None  # 推文的链表头结点
            self.follow(self.id)  # 关注自己

        # 用户关注一个人
        def follow(self, userId: int):
            self.followed.add(userId)

        # 用户取消关注一个人
        def unfollow(self, userId: int):
            # 不可以取关自己
            if userId != self.id and userId in self.followed:
                self.followed.remove(userId)

        # 用户发表一条推文
        def post(self, tweetId: int):
            global timestamp  # 全局时间戳，保证推文各不相同
            twt = Twitter.Tweet(tweetId, timestamp)
            timestamp += 1  # 时间戳自增
            # 将新建的推文插入链表头
            # 越靠前的推文 time 值越大
            twt.next = self.head
            self.head = twt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97