[LeetCode] 355. Design Twitter

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and is able to see the 10 most recent tweets in the user's news feed.

Implement the Twitter class:

• Twitter() Initializes your twitter object.
• void postTweet(int userId, int tweetId) Composes a new tweet with ID tweetId by the user userId. Each call to this function will be made with a unique tweetId.
• List<Integer> getNewsFeed(int userId) Retrieves the 10 most recent tweet IDs in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user themself. Tweets must be ordered from most recent to least recent.
• void follow(int followerId, int followeeId) The user with ID followerId started following the user with ID followeeId.
• void unfollow(int followerId, int followeeId) The user with ID followerId started unfollowing the user with ID followeeId.

Example 1:

Input
["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"]
[[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]
Output
[null, null, [5], null, null, [6, 5], null, [5]]

Explanation
Twitter twitter = new Twitter();
twitter.postTweet(1, 5); // User 1 posts a new tweet (id = 5).
twitter.getNewsFeed(1);  // User 1's news feed should return a list with 1 tweet id -> [5]. return [5]
twitter.follow(1, 2);    // User 1 follows user 2.
twitter.postTweet(2, 6); // User 2 posts a new tweet (id = 6).
twitter.getNewsFeed(1);  // User 1's news feed should return a list with 2 tweet ids -> [6, 5]. Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
twitter.unfollow(1, 2);  // User 1 unfollows user 2.
twitter.getNewsFeed(1);  // User 1's news feed should return a list with 1 tweet id -> [5], since user 1 is no longer following user 2.

Constraints:

• 1 <= userId, followerId, followeeId <= 500
• 0 <= tweetId <= 104
• All the tweets have unique IDs.
• At most 3 * 104 calls will be made to postTweet, getNewsFeed, follow, and unfollow.

设计推特。

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/design-twitter
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这是一道很经典的设计题，几个函数都不是很难，需要细心。建议可以先做一下 23 题合并 K 个单链表。

其中，每个用户写的推文需要自己写一个 class，因为需要记录推文的 ID，时间戳和下一个推文（用单链表连接）。对于同一个用户而言，他的推文的单链表的头结点是离当前时间最近发表的推文。当我们需要返回最近的 10 条推文的时候，我们就可以像 23 题那样，合并所有我关注的用户的推文，然后按照时间戳倒序找出最近的 10 条推文。图解可以参考这个帖子。

Java实现

  1 class Twitter {
  2     private HashMap<Integer, Tweet> twitter;
  3     private HashMap<Integer, Set<Integer>> followings;
  4     private static int timestamp = 0;
  5     private static PriorityQueue<Tweet> maxHeap;
  6 
  7     public Twitter() {
  8         followings = new HashMap<>();
  9         twitter = new HashMap<>();
 10         maxHeap = new PriorityQueue<>((a, b) -> b.timestamp - a.timestamp);
 11     }
 12     
 13     // 推特消息是按时间戳倒序放的
 14     // 离当前时间最近的推特在头结点
 15     public void postTweet(int userId, int tweetId) {
 16         timestamp++;
 17         if (twitter.containsKey(userId)) {
 18             Tweet oldHead = twitter.get(userId);
 19             Tweet newHead = new Tweet(tweetId, timestamp);
 20             newHead.next = oldHead;
 21             twitter.put(userId, newHead);
 22         } else {
 23             twitter.put(userId, new Tweet(tweetId, timestamp));
 24         }
 25     }
 26     
 27     public List<Integer> getNewsFeed(int userId) {
 28         maxHeap.clear();
 29         if (twitter.containsKey(userId)) {
 30             maxHeap.offer(twitter.get(userId));
 31         }
 32         Set<Integer> followingList = followings.get(userId);
 33         if (followingList != null && followingList.size() > 0) {
 34             for (Integer followingId : followingList) {
 35                 Tweet tweet = twitter.get(followingId);
 36                 if (tweet != null) {
 37                     maxHeap.offer(tweet);
 38                 }
 39             }
 40         }
 41 
 42         List<Integer> res = new ArrayList<>(10);
 43         int count = 0;
 44         while (!maxHeap.isEmpty() && count < 10) {
 45             Tweet cur = maxHeap.poll();
 46             res.add(cur.id);
 47             if (cur.next != null) {
 48                 maxHeap.offer(cur.next);
 49             }
 50             count++;
 51         }
 52         return res;
 53     }
 54     
 55     public void follow(int followerId, int followeeId) {
 56         if (followerId == followeeId) {
 57             return;
 58         }
 59         Set<Integer> followingList = followings.get(followerId);
 60         if (followingList == null) {
 61             Set<Integer> init = new HashSet<>();
 62             init.add(followeeId);
 63             followings.put(followerId, init);
 64         } else {
 65             if (followingList.contains(followeeId)) {
 66                 return;
 67             }
 68             followingList.add(followeeId);
 69         }
 70     }
 71     
 72     public void unfollow(int followerId, int followeeId) {
 73         if (followerId == followeeId) {
 74             return;
 75         }
 76         Set<Integer> followingList = followings.get(followerId);
 77         if (followingList == null) {
 78             return;
 79         }
 80         followingList.remove(followeeId);
 81     }
 82 
 83     class Tweet {
 84         private int id;
 85         private int timestamp;
 86         private Tweet next;
 87 
 88         public Tweet(int id, int timestamp) {
 89             this.id = id;
 90             this.timestamp = timestamp;
 91         }
 92     }
 93 }
 94 
 95 /**
 96  * Your Twitter object will be instantiated and called as such:
 97  * Twitter obj = new Twitter();
 98  * obj.postTweet(userId,tweetId);
 99  * List<Integer> param_2 = obj.getNewsFeed(userId);
100  * obj.follow(followerId,followeeId);
101  * obj.unfollow(followerId,followeeId);
102  */

LeetCode 题目总结