Lintcode501 Mini Twitter soluti

【题目描述】

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为空为止。

【参考答案】

www.jiuzhang.com/solutions/mini-twitter/