leetcode355. Design Twitter

栏目: 编程工具 · 发布时间: 4年前

内容简介:设计一个迷你推特,要求能够支持以下几个方法:发布推特,关注用户,取关用户,查看最近的十条关注用户发送的推特。这道题目本质上是考察是否能将数据结构的知识灵活的运用于现实生活中。从最直观的想法来看,我们会有一个用户实体,每个用户会记录自己关注的用户的id,以及记录自己发表的所有tweet。这里唯一的难点在于我们如何按照时间顺序获取tweet流。这么一想,这题其实就转换为如何将N个有序排列的数组汇合成一个有序的数组。这题等价于我们每次都会比较当前所有被关注者发布的最新未读tweet,选出结果后将其插入结果集。这里

题目要求

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:

postTweet(userId, tweetId): Compose a new tweet.
getNewsFeed(userId): 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.
follow(followerId, followeeId): Follower follows a followee.
unfollow(followerId, followeeId): Follower unfollows a followee.
Example:

Twitter twitter = new Twitter();

// User 1 posts a new tweet (id = 5).
twitter.postTweet(1, 5);

// User 1's news feed should return a list with 1 tweet id -> [5].
twitter.getNewsFeed(1);

// User 1 follows user 2.
twitter.follow(1, 2);

// User 2 posts a new tweet (id = 6).
twitter.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.
twitter.getNewsFeed(1);

// User 1 unfollows user 2.
twitter.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.
twitter.getNewsFeed(1);

设计一个迷你推特,要求能够支持以下几个方法:发布推特,关注用户,取关用户,查看最近的十条关注用户发送的推特。

思路和代码

这道题目本质上是考察是否能将数据结构的知识灵活的运用于现实生活中。从最直观的想法来看,我们会有一个用户实体,每个用户会记录自己关注的用户的id,以及记录自己发表的所有tweet。这里唯一的难点在于我们如何按照时间顺序获取tweet流。

这么一想,这题其实就转换为如何将N个有序排列的数组汇合成一个有序的数组。这题等价于我们每次都会比较当前所有被关注者发布的最新未读tweet,选出结果后将其插入结果集。这里我们可以利用等价队列帮助我们更快的完成选择的过程。

public class Twitter {

    
    public Twitter() {
        users = new HashMap<>();
    }
    
    public static int timestamp = 0;
    private Map<Integer, User> users;
    
    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
        if(!users.containsKey(userId)) {
            User user = new User(userId);
            users.put(userId, user);
        }
        
        User user = users.get(userId);
        user.tweet(tweetId);
    }
    
    /** 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> result = new ArrayList<Integer>();
        if(!users.containsKey(userId)) {
            return result;
        }
        User user = users.get(userId);
        
        PriorityQueue<Tweet> queue = new PriorityQueue<>(user.followed.size());
        for(int followee : user.followed) {
            User tmp = users.get(followee);
            if(tmp != null && tmp.headTweet != null) {
                queue.offer(tmp.headTweet);
            } 
        }
        
        while(!queue.isEmpty() && result.size() < 10) {
            Tweet t = queue.poll();
            result.add(t.tweetId);
            if(t.next != null) {
                queue.offer(t.next);
            }
        }
        return result;
    }
    
    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    public void follow(int followerId, int followeeId) {
        if(!users.containsKey(followerId)) {
            User user = new User(followerId);
            users.put(followerId, user);
        }
        if(!users.containsKey(followeeId)) {
            User user = new User(followeeId);
            users.put(followeeId, user);
        }
        
        User user = users.get(followerId);
        user.follow(followeeId);
    }
    
    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    public void unfollow(int followerId, int followeeId) {
        if(!users.containsKey(followerId) || followerId == followeeId) {
            return;
        }
      
        
        User user = users.get(followerId);
        user.unfollow(followeeId);
    }
    
    public static class User{
        
        int userId;
        
        Set<Integer> followed;
        
        Tweet headTweet;
        
        public User(int userId) {
            this.userId = userId;
            this.followed = new HashSet<>();
            follow(userId);
        }
        
        public void follow(int userId) {
            followed.add(userId);
        }
        
        public void unfollow(int userId) {
            followed.remove(userId);
        }
        
        public void tweet(int tweetId) {
            Tweet tweet = new Tweet(tweetId);
            tweet.next = headTweet;
            headTweet = tweet;
        }
        
    }
    
    public static class Tweet implements Comparable<Tweet>{
        
        int tweetId;
        
        Tweet next;
        
        int time;
        
        public Tweet(int tweetId) {
            this.tweetId = tweetId;
            this.time = timestamp++;
        }

        @Override
        public int compareTo(Tweet o) {
            return o.time - this.time;
        }
    }
}

以上所述就是小编给大家介绍的《leetcode355. Design Twitter》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

黑客

黑客

Steven Levy / 赵俐、刁海鹏、田俊静 / 机械工业出版社华章公司 / 2011-10-31 / 69.00元

黑客文化和伦理的奠基之作,计算机专业人士必读。 二十五周年新版,涵盖比尔·盖茨、马克·扎克伯格、理查德·斯托曼、史蒂夫·沃兹尼克等著名黑客的最新资料。 多年前,射击游戏之父、Doom游戏的作者约翰·卡马克由于读到本书,坚定了游戏开发的决心。 谷歌首席信息官本·弗里德也是本书的忠实读者。 探寻黑客文化的本质,体会黑客精神的精髓。一起来看看 《黑客》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具