leetcode 355 设计推特

用链表存储用户发送的每一个推特，用堆获取最先的10条动态

class Twitter {Map<Integer,Set<Integer>> followMap;//规定最新的放到最后Map<Integer,Tweet> postMap;//优先队列(堆）PriorityQueue<Tweet> priorityQueue;int timeStamp = 0;int limit = 10;public Twitter() {followMap = new HashMap();postMap = new HashMap<>();//按照每一个推特发送的时间戳由大到小排布priorityQueue = new PriorityQueue<>((t1,t2) -> t2.timeStamp - t1.timeStamp);}//userId发送推特public void postTweet(int userId, int tweetId) {//首先根据postMap来获取userId对应发送到文章Tweet tweet = postMap.get(userId);//生成新的tweetTweet newTweet = new Tweet(tweetId, timeStamp++, tweet);postMap.put(userId,newTweet);}//根据userId获得自己和关注用户的10条推特，按时间顺序由近到远排序public List<Integer> getNewsFeed(int userId) {//因为每一个用户都有自己的优先队列，所以先清空优先队列priorityQueue.clear();//将自己和关注的用户发送的最新的推特id先放入到优先队列if (postMap.containsKey(userId))priorityQueue.offer(postMap.get(userId));Set<Integer> follows = followMap.get(userId);if (follows != null){for (Integer follow : follows) {if (postMap.containsKey(follow))priorityQueue.offer(postMap.get(follow));}}//现在用户和所有关注的推特都已经放入到优先队列，开始获取前10条int count = 0;ArrayList<Integer> result = new ArrayList<>();while (!priorityQueue.isEmpty() && count < limit){//获取头部,在优先队列中删除Tweet tweet = priorityQueue.poll();result.add(tweet.id);if (tweet.next != null)priorityQueue.offer(tweet.next);count++;}return result;}//关注public void follow(int followerId, int followeeId) {// 被关注人不能是自己if (followeeId == followerId) {return;}Set<Integer> follows = followMap.getOrDefault(followerId, new HashSet<>());follows.add(followeeId);followMap.put(followerId,follows);}//取关public void unfollow(int followerId, int followeeId) {// 被关注人不能是自己if (followeeId == followerId) {return;}Set<Integer> follows = followMap.getOrDefault(followerId, new HashSet<>());follows.remove(followeeId);followMap.put(followerId,follows);}
}
class Tweet{int id;int timeStamp;Tweet next;public Tweet(int id, int timeStamp) {this.id = id;this.timeStamp = timeStamp;}public Tweet(int id, int timeStamp, Tweet next) {this.id = id;this.timeStamp = timeStamp;this.next = next;}
}/*** 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);*/