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);
        //生成新的tweet
        Tweet 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);
 */