思路

在推送给用户的推特，是该用户关注的人发的推特，并通过时间顺序合并在一起。采用多路归并的方式合并，在归并时，通过最小堆优化。

题目

设计一个简化版的推特(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 次

代码

type Twitter struct {
    users  map[int]*User
    serial int
}

type User struct {
    twitHeader *Twit
    follower   map[int]int
}

type Twit struct {
    id     int
    serial int
    next   *Twit
}

func Constructor() Twitter {
    return Twitter{
        users:  map[int]*User{},
        serial: 0,
    }
}

func (this *Twitter) PostTweet(userId int, tweetId int) {
    user := this.users[userId]
    if user == nil {
        user = &User{
            twitHeader: &Twit{},
            follower:   map[int]int{},
        }
        // bug 没有自己关注自己，下次做题先记录重点
        user.follower[userId] = 1
        this.users[userId] = user
    }
    this.serial++
    twit := Twit{id: tweetId, serial: this.serial}
    twit.next = user.twitHeader.next
    user.twitHeader.next = &twit
}

func (this *Twitter) GetNewsFeed(userId int) []int {
    user := this.users[userId]
    // bug 边界问题
    if user == nil {
        return nil
    }

    // 获取所有关注用户的帖子
    twits := make([]*Twit, len(user.follower))
    i := 0
    for id, _ := range user.follower {
        twits[i] = this.users[id].twitHeader
        i++
    }

    // 合并关注用户的帖子
    minHeap := MinHeap{}
    heap.Init(&minHeap)
    for _, twit := range twits {
        if twit.next != nil {
            // bug 堆使用方式错误
            heap.Push(&minHeap, twit.next)
        }
    }

    var res []int
    // bug 最近10条，下次做题先记录重点
    for minHeap.Len() > 0 && len(res) < 10 {
        // bug 堆使用方式错误
        e := heap.Pop(&minHeap)
        twit := e.(*Twit)
        res = append(res, twit.id)
        if twit.next != nil {
            heap.Push(&minHeap, twit.next)
        }
    }

    // bug，边界问题
    if len(res) == 0 {
        return nil
    }
    return res
}

func (this *Twitter) Follow(followerId int, followeeId int) {
    user := this.users[followerId]
    if user == nil {
        user = &User{
            twitHeader: &Twit{},
            follower:   map[int]int{},
        }
        user.follower[followerId] = 1
        this.users[followerId] = user
    }

    // bug，边界问题
    followee := this.users[followeeId]
    if followee == nil {
        followee = &User{
            twitHeader: &Twit{},
            follower:   map[int]int{},
        }
        followee.follower[followeeId] = 1
        this.users[followeeId] = followee
    }

    user.follower[followeeId] = 1
}

func (this *Twitter) Unfollow(followerId int, followeeId int) {
    user := this.users[followerId]
    // bug，边界问题
    if user == nil {
        return
    }
    delete(user.follower, followeeId)
}

// An MinHeap295 is a min-heap of ints.
// bug 没有用指针，使用姿势统一
type MinHeap []*Twit

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].serial > h[j].serial }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x any) {
    // Push and Pop use pointer receivers because they modify the slice's length,
    // not just its contents.
    *h = append(*h, x.(*Twit))
}

func (h *MinHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}