一、题目描述
设计一个简化版的推特(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 <= 10^4
- 所有推特的 ID 都互不相同
postTweet
、getNewsFeed
、follow
和unfollow
方法最多调用3 * 10^4
次
二、解题思路
-
使用一个数据结构来存储推文,可以使用列表或链表,列表中的每个元素代表一条推文,包含推文ID和用户ID。考虑到需要频繁地在头部插入新推文,使用链表结构更合适。
-
使用一个哈希表来存储用户关注关系,键为用户ID,值为该用户关注的所有用户ID集合。
-
postTweet
方法:在推文链表的头部插入一条新推文。 -
getNewsFeed
方法:遍历推文链表,找出当前用户和其关注用户的推文,按时间顺序排序,取前10条推文。 -
follow
方法:在关注关系的哈希表中,将关注者ID添加到被关注者的关注者集合中。 -
unfollow
方法:在关注关系的哈希表中,将关注者ID从被关注者的关注者集合中移除。
三、具体代码
import java.util.*;public class Twitter {private static class Tweet {int time;int tweetId;Tweet next;public Tweet(int time, int tweetId) {this.time = time;this.tweetId = tweetId;this.next = null;}}private Map<Integer, Set<Integer>> follows;private Map<Integer, Tweet> tweets;private int timeStamp;public Twitter() {follows = new HashMap<>();tweets = new HashMap<>();timeStamp = 0;}public void postTweet(int userId, int tweetId) {Tweet newTweet = new Tweet(timeStamp++, tweetId);newTweet.next = tweets.get(userId);tweets.put(userId, newTweet);}public List<Integer> getNewsFeed(int userId) {List<Tweet> list = new ArrayList<>();// 添加当前用户的推文if (tweets.containsKey(userId)) {list.add(tweets.get(userId));}// 添加关注用户的推文if (follows.containsKey(userId)) {for (int followeeId : follows.get(userId)) {if (tweets.containsKey(followeeId)) {list.add(tweets.get(followeeId));}}}// 按时间排序list.sort((a, b) -> b.time - a.time);List<Integer> res = new ArrayList<>();for (Tweet tweet : list) {while (tweet != null && res.size() < 10) {res.add(tweet.tweetId);tweet = tweet.next;}}return res;}public void follow(int followerId, int followeeId) {follows.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);}public void unfollow(int followerId, int followeeId) {if (follows.containsKey(followerId)) {follows.get(followerId).remove(followeeId);}}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
-
Twitter
构造函数:- 初始化数据结构,时间复杂度为O(1)。
-
postTweet
方法:- 每次调用时,直接在哈希表中插入新的推文节点,时间复杂度为O(1)。
-
getNewsFeed
方法:- 遍历所有关注者的推文,最坏情况下,如果用户关注了所有其他用户,时间复杂度为O(N),其中N是用户数量。
- 将所有推文节点加入列表,时间复杂度为O(N)。
- 对推文列表进行排序,时间复杂度为O(MlogM),其中M是推文总数。
- 遍历排序后的推文列表以获取前10条推文,最坏情况下时间复杂度为O(M)。
- 综合起来,
getNewsFeed
的时间复杂度为O(N + MlogM + M)。
-
follow
方法:- 在哈希表中添加关注关系,时间复杂度为O(1)。
-
unfollow
方法:- 在哈希表中移除关注关系,时间复杂度为O(1)。
2. 空间复杂度
-
Twitter
构造函数:- 初始化了两个哈希表和一个整数,空间复杂度为O(N),其中N是用户数量。
-
postTweet
方法:- 每次调用时,创建一个新的推文节点,空间复杂度为O(1)。
-
getNewsFeed
方法:- 创建了一个推文列表,最坏情况下,列表的大小为所有用户推文的总数M,空间复杂度为O(M)。
-
follow
方法:- 在哈希表中添加关注关系,空间复杂度为O(1)。
-
unfollow
方法:- 移除哈希表中的关注关系,空间复杂度为O(1)。
总体空间复杂度:
综上所述,该Twitter类的时间复杂度和空间复杂度分别为O(N + MlogM + M)和O(N^2 + M)。
五、总结知识点
-
静态内部类:
Tweet
类被定义为Twitter
类的静态内部类,用于表示一条推文,包含时间戳、推文ID和指向下一条推文的引用。
-
数据结构:
-
时间戳:
- 使用一个整数
timeStamp
作为全局时间戳,每次发推时递增,用于确定推文的顺序。
- 使用一个整数
-
构造函数:
Twitter
类的构造函数初始化了两个哈希表follows
和tweets
,以及时间戳timeStamp
。
-
方法重载:
postTweet
、getNewsFeed
、follow
和unfollow
方法是Twitter
类的成员方法,用于实现推文发布、获取新闻源、关注和取消关注的功能。
-
链表操作:
-
集合操作:
- 使用
HashMap
的computeIfAbsent
方法来安全地添加关注关系,避免空指针异常。 - 使用
HashSet
的add
和remove
方法来管理关注列表。
- 使用
-
排序算法:
- 在
getNewsFeed
方法中,使用List
的sort
方法结合自定义比较器来对推文按时间戳降序排序。
- 在
-
迭代器使用:
- 在
getNewsFeed
方法中,使用迭代器遍历推文链表,并收集推文ID。
- 在
-
条件判断:
- 在
getNewsFeed
、follow
和unfollow
方法中,使用了条件判断来处理边界情况和异常情况。
- 在
以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。