【题目描述】
Implement a simple twitter. Support the following method:
1.postTweet(user_id, tweet_text). Post a tweet.
2.getTimeline(user_id). Get the given user's most recently 10 tweets posted by himself, order by timestamp from most recent to least recent.
3.getNewsFeed(user_id). Get the given user's most recently 10 tweets in his news feed (posted by his friends and himself). Order by timestamp from most recent to least recent.
4.follow(from_user_id, to_user_id). from_user_id followed to_user_id.
5.unfollow(from_user_id, to_user_id). from_user_id unfollowed to to_user_id.
实现一个迷你的推特,支持下列几种方法
1.postTweet(user_id, tweet_text). 发布一条推特.
2.getTimeline(user_id). 获得给定用户最新发布的十条推特,按照发布时间从最近的到之前排序
3.getNewsFeed(user_id). 获得给定用户的朋友或者他自己发布的最新十条推特,从发布时间最近到之前排序
4.follow(from_user_id, to_user_id). from_user_id 关注 to_user_id.
5.unfollow(from_user_id, to_user_id). from_user_id 取消关注 to_user_id.
【题目链接】
www.lintcode.com/en/problem/mini-twitter/
【题目解析】
Map + Set + PriorityQueue
系统应当维护下列信息:
1). 一个全局的推文计数器:postCount 用户发推文时,计数器+1
2). 推文Id -> 推文计数器的映射:tweetIdMap 用来记录推文的次序
3). 推文Id -> 用户Id的映射:tweetOwnerMap 用来记录推文的发送者是谁
4). 用户Id -> 关注对象集合的映射: followeeMap 用来记录用户的关注对象(关注/取消关注)
方法的实现:
1). 关注 follow / 取消关注 unfollow:
只需要维护followeeMap中对应的关注对象集合followeeSet即可
2). 发送推文 postTweet:
更新推文计数器postCount,维护tweetIdMap;
向用户的推文发送列表中新增一条记录
3). 获取推文推送 getNewsFeed:
这里需要使用优先队列PriorityQueue,记为pq
遍历用户的关注对象列表,将每一位关注对象的最新一条推文添加至pq中。
然后从pq中弹出最近的一条推文,记为topTweetId;
通过tweetOwnerMap找到这条推文的发送者userId,然后将该发送者的下一条比较新的推文添加至pq。
直到弹出10条最新的推文,或者pq为空为止。
【参考答案】