355. Design Twitter #

题目 #

设计一个简化版的推特，让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近 10 条推文。

实现 Twitter 类：

Twitter() 初始化简易版推特对象
void postTweet(int userId, int tweetId) 根据给定的 tweetId 和 userId 创建一条新推文。每次调用此函数都会使用一个不同的 tweetId。
List<Integer> getNewsFeed(int userId) 检索当前用户新闻推送中最近 10 条推文的 ID。新闻推送中的每一项都必须是由用户关注的人或者是用户自己发布的推文。推文必须 按照时间顺序由最近到最远排序。
void follow(int followerId, int followeeId) ID 为 followerId 的用户开始关注 ID 为 followeeId 的用户。
void unfollow(int followerId, int followeeId) ID 为 followerId 的用户不再关注 ID 为 followeeId 的用户。

思路 #

哈希表 存储用户的关注列表。
单链表 存储用户的推文链表。
优先级队列 实现按时间戳排序的推文链表的合并。
大顶堆 实现最近 N 条推文的获取。

代码 #

class Twitter {
    private class ListNode implements Comparable<ListNode> {
        public int timestamp;
        public int tweetId;
        public ListNode next;
        
        ListNode(int timestamp, int tweetId, ListNode next) {
            this.timestamp = timestamp;
            this.tweetId = tweetId;
            this.next = next;
        }
        
        public int compareTo(ListNode other) {
            return other.timestamp - this.timestamp;
        }
    }
    
    private class User {
        public int userId;
        public ListNode tweets;
        public Set<User> following;
        
        User(int userId, ListNode tweets) {
            this.userId = userId;
            this.tweets = tweets;
            
            this.following = new HashSet<>();
            this.following.add(this);
        }
    }
    
    private Map<Integer, User> map;
    private int timestamp;
    
    public void postTweet(int userId, int tweetId) {
        if (this.map.containsKey(userId) == false) this.map.put(userId, new User(userId, null));
        User user = this.map.get(userId);
        
        this.timestamp += 1;
        user.tweets = new ListNode(this.timestamp, tweetId, user.tweets);
    }
    
    public List<Integer> getNewsFeed(int userId) {
        List<Integer> newsFeed = new ArrayList<>();
        
        PriorityQueue<ListNode> queue = new PriorityQueue<>();
        
        if (this.map.containsKey(userId) == false) this.map.put(userId, new User(userId, null));
        
        for (User player: this.map.get(userId).following) {
            if (player.tweets != null) {
                queue.offer(player.tweets);
            }
        }
        
        while (newsFeed.size() < 10 && queue.size() != 0) {
            ListNode tweets = queue.poll();
            newsFeed.add(tweets.tweetId);
            if (tweets.next != null) queue.offer(tweets.next);
        }
        
        return newsFeed;
    }
    
    public void follow(int followerId, int followeeId) {
        if (this.map.containsKey(followerId) == false) this.map.put(followerId, new User(followerId, null));
        if (this.map.containsKey(followeeId) == false) this.map.put(followeeId, new User(followeeId, null));
        
        User follower = this.map.get(followerId), followee = this.map.get(followeeId);
        follower.following.add(followee);
    }
    
    public void unfollow(int followerId, int followeeId) {
        User follower = this.map.get(followerId), followee = this.map.get(followeeId);
        follower.following.remove(followee);
    }
}

致谢 #

liweiwei