leetcode355. Design Twitter

题目要求

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;
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode363. Max Sum of Rectangle No Larger Than K

    现有一个由整数构成的矩阵,问从中找到一个子矩阵,要求该子矩阵中各个元素的和为不超过k的最大值,问子矩阵中元素的和为多少? 注:后面的文章中将使用[左上角顶点坐标...

    眯眯眼的猫头鹰
  • leetcode540. Single Element in a Sorted Array

    You are given a sorted array consisting of only integers where every element app...

    眯眯眼的猫头鹰
  • leetcode365. Water and Jug Problem

    假设现在有两个杯子,每个杯子分别最多可以装x和y升水,假设现在水的供应量是无限的,问是否有可能用这两个杯子共同承装z升水,可以用两个杯子执行的操作如下:

    眯眯眼的猫头鹰
  • bs4--mechanize模拟浏览器

    如果非要使用py3,可以使用mechanicalsoup模块(网上大概看了下,都说不好用,这里不多介绍)

    py3study
  • 学界 | 李飞飞最新论文:结合深度学习和谷歌街景来估算美国人口结构

    AI科技评论按:最近,一篇名为《Using Deep Learning and Google Street View to Estimate the Demog...

    AI科技评论
  • 基于Spring的Web缓存 转

    原文:https://www.cnblogs.com/moongeek/p/7689683.html

    wuweixiang
  • 标签之美三——超链接的嵌入 原

    通常的超链接有两种方式,一种是链接到另一个文件,另一种是链接到当前文件的某个位置。这两种方式都是通过<a></a>标签来创建,其中href属性用来指定链接的目标...

    珲少
  • C#开发中Windows域认证登录

    吉日嘎了的Webform例子程序做的很好,但在我们公司,除了使用GPM通用权限管理自带的账户系统登录,还需要集成Windows域账户登录。对于如何实现,我思考了...

    崔文远TroyCui
  • 模拟微信下拉页面

    在安卓下 始终不够完美,今天遇到了 iscroll.js,使用 iscroll.js 重新写了一个版本,现在比较完美了。

    墨渊
  • jquery 置顶按钮

    这个图片我用了阿里的矢量图库,如果不懂如何使用的朋友,可以访问iconfont阿里巴巴矢量图标库从注册到使用。

    Devops海洋的渔夫

扫码关注云+社区

领取腾讯云代金券