问题：
Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user's news feed. Your design should support the following methods:
Example:
Twitter = new Twitter(); // User 1 posts a new tweet (id = 5). .postTweet(1, 5); // User 1's news feed should return a list with 1 tweet id -> [5]. .getNewsFeed(1); // User 1 follows user 2. .follow(1, 2); // User 2 posts a new tweet (id = 6). .postTweet(2, 6); // User 1's news feed should return a list with 2 tweet ids -> [6, 5]. // Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5. .getNewsFeed(1); // User 1 unfollows user 2. .unfollow(1, 2); // User 1's news feed should return a list with 1 tweet id -> [5], // since user 1 is no longer following user 2. .getNewsFeed(1);
解决：
① 维护一个人员表，维护一个表。注意getNewsFeed(userId)获取最近10条。
class Twitter {//283ms
class TwitterNode{
int userId;
int tweetId;
public TwitterNode(int userId,int tweetId){
this.userId = userId;
this.tweetId = tweetId;
}
}
List<TwitterNode> NodeList;//记录
Map<Integer,Set<Integer>> userManager;//记录用户，键为userId，值为该user关注的userId
/** Initialize your data structure here. */
public Twitter() {
NodeList = new ArrayList<>();
userManager = new HashMap<>();
}
/** Compose a new tweet. */
public void postTweet(int userId, int tweetId) {
if (! userManager.containsKey(userId)){//不存在该用户
Set<Integer> set = new HashSet<>();
set.add(userId);
userManager.put(userId,set);
}
TwitterNode node = new TwitterNode(userId,tweetId);
NodeList.add(0,node);
}
/** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
public List<Integer> getNewsFeed(int userId) {
List<Integer> res = new ArrayList<>();
if (userManager.containsKey(userId)){
Set<Integer> follows = userManager.get(userId);
int count = 0;
for (TwitterNode curNode : NodeList){
if (count == 10){
break;
}
if (follows.contains(curNode.userId)){
res.add(curNode.tweetId);
count ++;
}
}
}
return res;
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
public void follow(int followerId, int followeeId) {
Set<Integer> follows;
if (! userManager.containsKey(followeeId)){//被关注者必须存在
follows = new HashSet<>();
follows.add(followeeId);
userManager.put(followeeId,follows);
}
if (! userManager.containsKey(followerId)){
follows = new HashSet<>();
follows.add(followerId);
userManager.put(followerId,follows);
}
userManager.get(followerId).add(followeeId);
}
/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
public void unfollow(int followerId, int followeeId) {
if (followerId != followeeId && userManager.containsKey(followerId)){
if (userManager.containsKey(followeeId)){
userManager.get(followerId).remove(followeeId);
}
}
}
}
/**
* Your Twitter object will be instantiated and called as such:
* Twitter obj = new Twitter();
* obj.postTweet(userId,tweetId);
* List<Integer> param_2 = obj.getNewsFeed(userId);
* obj.follow(followerId,followeeId);
* obj.unfollow(followerId,followeeId);
*/
② 在discuss中看到的，要用PriorityQueue根据插入时间对用户所拥有的tweet进行排序。
class Twitter {//172ms
class Tweet{
int tweetId;
int time;
Tweet next;//记录该用户发布的tweet列表的下一个
public Tweet(int tweetId){
this.tweetId = tweetId;
time = timeStamp ++;
next = null;
}
}
class User{
int userId;
Tweet first;
Set<Integer> follows;//该用户关注的用户
public User(int userId){
this.userId = userId;
follows = new HashSet<>();
follows.add(userId);//首先包括该用户自己
first = null;
}
public void post(int tweetId){
Tweet newTweet = new Tweet(tweetId);
newTweet.next = first;
first = newTweet;
}
public void follow(int userId){
follows.add(userId);
}
public void unfollow(int userId){
follows.remove(userId);
}
}
int timeStamp;//添加时间戳，将PriorityQueue中的tweet按发布时间排序
Map<Integer,User> userMap;
public Twitter(){
userMap = new HashMap<>();
}
public void postTweet(int userId,int tweetId){
if (! userMap.containsKey(userId)){
User newUser = new User(userId);
userMap.put(userId,newUser);
}
userMap.get(userId).post(tweetId);
}
public List<Integer> getNewsFeed(int userId){
List<Integer> res = new ArrayList<>();
if (! userMap.containsKey(userId)){
return res;
}
Set<Integer> follows = userMap.get(userId).follows;//获取用户关注的user
PriorityQueue<Tweet> tweets = new PriorityQueue<>((a,b) -> (b.time - a.time));//记录该用户包含的tweets，并按时间排序
for (int user : follows){//更新用户的tweets
Tweet tweet = userMap.get(user).first;
if (tweet != null){
tweets.add(tweet);
}
}
int count = 0;
while(! tweets.isEmpty() && count < 10){
Tweet tweet = tweets.poll();
res.add(tweet.tweetId);
count ++;
if (tweet.next != null) tweets.add(tweet.next);
}
return res;
}
public void follow(int followerId,int followeeId){
if (! userMap.containsKey(followerId)){
User newUser = new User(followerId);
userMap.put(followerId,newUser);
}
if (! userMap.containsKey(followeeId)){
User newUser = new User(followeeId);
userMap.put(followeeId,newUser);
}
userMap.get(followerId).follow(followeeId);
}
public void unfollow(int followerId,int followeeId){
if (! userMap.containsKey(followerId) || followerId == followeeId){
return;
}
userMap.get(followerId).unfollow(followeeId);
}
}