LeetCode刷题实战355：设计推特
共 9821字，需浏览 20分钟
· 2021-08-19
postTweet(userId, tweetId): 创建一条新的推文
getNewsFeed(userId): 检索最近的十条推文。每个推文都必须是由此用户关注的人或者是用户自己发出的。推文必须按照时间顺序由最近的开始排序。
follow(followerId, followeeId): 关注一个用户
unfollow(followerId, followeeId): 取消关注一个用户
示例
Twitter twitter = new Twitter();
// 用户1发送了一条新推文 (用户id = 1, 推文id = 5).
twitter.postTweet(1, 5);
// 用户1的获取推文应当返回一个列表，其中包含一个id为5的推文.
twitter.getNewsFeed(1);
// 用户1关注了用户2.
twitter.follow(1, 2);
// 用户2发送了一个新推文 (推文id = 6).
twitter.postTweet(2, 6);
// 用户1的获取推文应当返回一个列表，其中包含两个推文，id分别为 -> [6, 5].
// 推文id6应当在推文id5之前，因为它是在5之后发送的.
twitter.getNewsFeed(1);
// 用户1取消关注了用户2.
twitter.unfollow(1, 2);
// 用户1的获取推文应当返回一个列表，其中包含一个id为5的推文.
// 因为用户1已经不再关注用户2.
twitter.getNewsFeed(1);
解题
发布动态的时候，需要先判断用户是否存在，如果存在，新增发布信息，如果不存在，需要新建立用户发布信息。
用户关注其他用户的时候，如果用户不存在，需要创建用户并添加关注用户。
用户取消关注的时候，需要判断用户是否存在，如果存在，则删除关注用户，否则不操作。
获取用户最新10条动态的时候，需要采用优先队列辅助解决，当用户存在的时候，需要获取用户的关注对象和用户自身发布的所有推文信息，借助优先队列获取最新发布的10条信息。
public class Twitter {
//代表发布的先后顺序
private static int pubNum = 0;
private class TwitterNews {
private int tweetId;
private int pubTime;
public TwitterNews(int tweetId) {
pubNum = pubNum + 1;
this.tweetId = tweetId;
this.pubTime = pubNum;
}
}
private class TwitterUser {
private int userId;
/**
* 用户的关注对象
*/
private HashSet<Integer> userFollows;
/**
* 用户发布的信息对象
*/
private HashSet<TwitterNews> userPubNews;
TwitterUser(int userId) {
this.userId = userId;
this.userFollows = new HashSet<>();
this.userPubNews = new LinkedHashSet<TwitterNews>();
}
}
private HashMap<Integer, TwitterUser> IDToUser;
public Twitter() {
IDToUser = new HashMap<Integer, TwitterUser>();
}
/**
* 发布一条动态
* @param userId
* @param tweetId
*/
public void postTweet(int userId, int tweetId) {
TwitterNews twitterNews = new TwitterNews(tweetId);
if (IDToUser.containsKey(userId)) {
TwitterUser tweetUser = IDToUser.get(userId);
tweetUser.userPubNews.add(twitterNews);
} else {
TwitterUser tweetUser = new TwitterUser(userId);
tweetUser.userPubNews.add(twitterNews);
IDToUser.put(userId, tweetUser);
}
}
/**
* 获取最新的动态发布信息
* @param userId
* @return
*/
public List<Integer> getNewsFeed(int userId) {
if (!IDToUser.containsKey(userId)) {
return new ArrayList<>();
}
PriorityQueue<TwitterNews> queue = new PriorityQueue<TwitterNews>(((o1, o2) -> o2.pubTime - o1.pubTime));
HashSet<Integer> userFollows = IDToUser.get(userId).userFollows;
userFollows.add(userId);
for (int userID : userFollows) {
TwitterUser twitterUser = IDToUser.get(userID);
/**
* 没有用户则继续寻找下一个用户
*/
if (twitterUser == null) {
continue;
}
HashSet<TwitterNews> userPubNews = twitterUser.userPubNews;
for (TwitterNews userPubNew : userPubNews) {
queue.add(userPubNew);
}
}
List<Integer> res = new ArrayList<>();
while (!queue.isEmpty()) {
if (res.size() == 10) {
break;
}
TwitterNews twitterNews = queue.poll();
res.add(twitterNews.tweetId);
}
return res;
}
/**
* 添加关注人
* @param followerId
* @param followeeId
*/
public void follow(int followerId, int followeeId) {
if (IDToUser.containsKey(followerId)) {
TwitterUser tweetUser = IDToUser.get(followerId);
tweetUser.userFollows.add(followeeId);
} else {
TwitterUser tweetUser = new TwitterUser(followerId);
tweetUser.userFollows.add(followeeId);
IDToUser.put(followerId, tweetUser);
}
}
/**
* 取消关注人
* @param followerId
* @param followeeId
*/
public void unfollow(int followerId, int followeeId) {
if (IDToUser.containsKey(followerId)) {
TwitterUser tweetUser = IDToUser.get(followerId);
tweetUser.userFollows.remove(followeeId);
}
}
}