?LeetCode刷題實戰(zhàn)355：設計推特
postTweet(userId, tweetId): 創(chuàng)建一條新的推文
getNewsFeed(userId): 檢索最近的十條推文。每個推文都必須是由此用戶關注的人或者是用戶自己發(fā)出的。推文必須按照時間順序由最近的開始排序。
follow(followerId, followeeId): 關注一個用戶
unfollow(followerId, followeeId): 取消關注一個用戶
示例
Twitter twitter = new Twitter();
// 用戶1發(fā)送了一條新推文 (用戶id = 1, 推文id = 5).
twitter.postTweet(1, 5);
// 用戶1的獲取推文應當返回一個列表，其中包含一個id為5的推文.
twitter.getNewsFeed(1);
// 用戶1關注了用戶2.
twitter.follow(1, 2);
// 用戶2發(fā)送了一個新推文 (推文id = 6).
twitter.postTweet(2, 6);
// 用戶1的獲取推文應當返回一個列表，其中包含兩個推文，id分別為 -> [6, 5].
// 推文id6應當在推文id5之前，因為它是在5之后發(fā)送的.
twitter.getNewsFeed(1);
// 用戶1取消關注了用戶2.
twitter.unfollow(1, 2);
// 用戶1的獲取推文應當返回一個列表，其中包含一個id為5的推文.
// 因為用戶1已經不再關注用戶2.
twitter.getNewsFeed(1);
解題
發(fā)布動態(tài)的時候，需要先判斷用戶是否存在，如果存在，新增發(fā)布信息，如果不存在，需要新建立用戶發(fā)布信息。
用戶關注其他用戶的時候，如果用戶不存在，需要創(chuàng)建用戶并添加關注用戶。
用戶取消關注的時候，需要判斷用戶是否存在，如果存在，則刪除關注用戶，否則不操作。
獲取用戶最新10條動態(tài)的時候，需要采用優(yōu)先隊列輔助解決，當用戶存在的時候，需要獲取用戶的關注對象和用戶自身發(fā)布的所有推文信息，借助優(yōu)先隊列獲取最新發(fā)布的10條信息。
public class Twitter {
//代表發(fā)布的先后順序
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;
/**
* 用戶發(fā)布的信息對象
*/
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>();
}
/**
* 發(fā)布一條動態(tài)
* @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);
}
}
/**
* 獲取最新的動態(tài)發(fā)布信息
* @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);
/**
* 沒有用戶則繼續(xù)尋找下一個用戶
*/
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);
}
}
}