题目
设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近 10 条推文。
实现 Twitter 类：
Twitter() 初始化简易版推特对象
void postTweet(int userId, int tweetId) 根据给定的 tweetId 和 userId 创建一条新推文。每次调用此函数都会使用一个不同的 tweetId 。
List 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.post服务器托管网Tweet(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
代码实现
class Twitter {
private class Node {
// 哈希表存储关注人的 Id
Set followee;
// 用链表存储 tweetId
LinkedList tweet;
Node() {
followee = new HashSet();
tweet = new LinkedList();
}
}
// getNewsFeed 检索的推文的上限以及 tweetId 的时间戳
private int recentMax, time;
// tweetId 对应发送的时间
private Map tweetTime;
// 每个用户存储的信息
private Map user;
public Twitter() {
time = 0;
recentMax = 10;
tweetTime = new HashMap();
user = new HashMap();
}
// 初始化
public void init(int userId) {
user.put(userId, new Node());
}
public void postTweet(int userId, int tweetId) {
if (!user.containsKey(userId)) {
init(userId);
}
// 达到限制，剔除链表末尾元素
if (user.get(userId).tweet.size() == recentMax) {
user.get(userId).tweet.remove(recentMax - 1);
}
user.get(userId).tweet.addFirst(tweetId);
tweetTime.put(tweetId, ++time);
}
public List getNewsFeed(int userId) {
LinkedList ans = new LinkedList();
for (int it : user.getOrDefault(userId, new Node()).tweet) {
ans.addLast(it);
}
for (int followeeId : user.getOrDefault(userId, new Node()).followee) {
if (followeeId == userId) { // 可能出现自己关注自己的情况
continue;
}
LinkedList res = new LinkedList();
int tweetSize = user.get(followeeId).tweet.size();
Iterator it = user.get(followeeId).tweet.iterator();
int i = 0;
int j = 0;
int curr = -1;
// 线性归并
if (j tweetTime.get(ans.get(i))) {
res.addLast(curr);
++j;
if (it.hasNext()) {
curr = it.next();
}
} else {
res.addLast(ans.get(i));
++i;
}
// 已经找到这两个链表合起来后最近的 recentMax 条推文
if (res.size() == recentMax) {
break;
}
}
}
for (; i (res);
}
return ans;
}
public void follow(int followerId, int followeeId) {
if (!user.containsKey(followerId)) {
init(followerId);
}
if (!user.containsKey(followeeId)) {
init(followeeId);
}
user.get(followerId).followee.add(followeeId);
}
public void unfollow(int followerId, int followeeId) {
user.getOrDefault(followerId, new Node()).followee.remove(followeeId);
}
}
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
PMP（Project Management Professional 项目管理专业人士资格认证，由全球最大的项目管理专业组织机构——美国PMI发起，目的是用来严格评估管理项目人员知识技能是否具有高品质的资格认证考试。给大家带来关于PMP考试的实用应试技巧。 …
