设计推特（Leetcode355）

例题：

https://leetcode.cn/problems/design-twitter/

分析：

推特其实类似于微博，在微博中可以发送文章。

求解这类题目，我们需要根据题目需求，利用面向对象的思想，先对需求做一个抽象，看看能抽象出哪些对象。可以看出，题目中有3个对象：推特对象、用户对象、文章对象。

下图表示这3类对象之间的关系：

我们知道，一个推特包含多个用户，推特和用户之间是一对多的关系，因此在推特类中可以创建一个map集合来保存用户数据；同样，一个用户可以发送多条文章，用户和文章也是一对多的关系，因为题目有一个方法，获取一个用户发送的近10条文章（其中包括关注者发送的），我们可以用一个链表来存储推文，在用户类中设置一个头节点。

一个用户也可以关注多个用户，用户与用户之间也是一对多的关系，可以用一个set集合存储关注的用户。

这里面有个方法getNewsFeed()获取最新的10篇文章， 包括自己发送的和关注者发送的，其实这就是一个多链表合并问题，按推文时间合并，可以采用大顶堆的方式把自己的推文和关注者的推文加入堆中，然后从堆中弹出一个最近的文章，然后再加入该链表的下一篇推文。

        ​​​​​     ​ 

如上图，假设①号链表 表示用户的推文，其它链表是关注者的推文，首先依次把 各链表的头节点加入堆中（10， 9， 3），在堆中弹出一篇最近的文章（10）。紧接着加入被弹出链表的下一个节点（6），再和其它链表头的元素相比选出最近的，依次类推。

代码实现：

package leetcodeup;import java.util.*;public class TwitterLeetcode355 {    static class Twitter {        public Twitter() {        }        static class Tweet{            int tweetId;            int time;            Tweet next;            public Tweet(int tweetId, int time, Tweet next) {                this.tweetId = tweetId;                this.time = time;                this.next = next;            }            public int getTweetId() {                return tweetId;            }            public int getTime() {                return time;            }        }        static class User{            int userId;            public User(int userId) {                this.userId = userId;            }            Tweet head = new Tweet(-1, -1, null);            Set followees = new HashSet();        }        private final Map userMap = new HashMap();        private static int time;        //发布文章        public void postTweet(int userId, int tweetId) {            User user = userMap.computeIfAbsent(userId, User::new);            user.head.next = new Tweet(tweetId, time++, user.head.next);        }        //新增关注        public void follow(int followerId, int followeeId) {            User user = userMap.computeIfAbsent(followerId, User::new);            User followee = userMap.computeIfAbsent(followeeId, User::new);            user.followees.add(followee.userId);        }        //取消关注        public void unfollow(int followerId, int followeeId) {            User user = userMap.get(followerId);            if(user != null){                user.followees.remove(followeeId);            }        }        //获取最新的10篇文章（包括自己和关注者）        public List getNewsFeed(int userId) {            PriorityQueue queue = new PriorityQueue(Comparator.comparingInt(Tweet::getTime).reversed());            User user = userMap.get(userId);            if(user == null){                return List.of();            }            if(user.head.next != null){                queue.offer(user.head.next);            }            Set followees = user.followees;            for (Integer id : followees) {                User followee = userMap.get(id);                if(followee.head.next != null){                    queue.offer(followee.head.next);                }            }            List res = new ArrayList();            int count = 0;            while(!queue.isEmpty() && count