找回密码
 立即注册

扫一扫,访问微社区

QQ登录

只需一步,快速开始

查看: 2781|回复: 0

[代码与实例] Lintcode501 Mini Twitter solution 题解

15

主题

15

帖子

15

积分

贫民

积分
15
Jenny 发表于 2018-7-4 21:59:01 | 显示全部楼层 |阅读模式
【题目描述】
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 times**p 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 times**p 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.

【题目解析】
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为空为止。




回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表