LeetCode——设计推特

NO.355 设计推特中等

思路一：哈希表+链表+堆 第一次遇到设计题感觉还是很棘手的，所以啰嗦一下的过程，为下次积攒经验。

推文实体：本题只考虑添加新推文，不需要删除、修改、随机访问。所以用单链表来实现，而且链表不需要考虑扩容的问题。每条推文包含id、时间戳、并作为链表节点。

private static class Tweet{
    public int id;
    public int time;
    public Tweet next;

    public Tweet(int id,int time){
        this.id=id;
        this.time=time;
        this.next=null;
    }
}

推特实体：构造方法、发一条推文方法、返回关注的人最新发的十条推文方法、关注一个人方法、取关一个人方法。推文时间的生成，用全局变量实现。

public class Twitter {
    //全局时间戳，每条博文发送前自增1
    private static int timestamp=0;

    //推文实体
    private class Tweet{...}

    //用户和推文列表的关系
    HashMap<Integer,Tweet> twitter;

    //用户和关注列表的关系
    HashMap<Integer, HashSet<Integer>> followed;
    
    //返回最近动态要用的数据结构，优先队列默认就是大顶堆
    PriorityQueue<Tweet> maxHeap;

    /** 初始化 */
    public Twitter() {}

    /** user 发表一条 tweet 动态 */
    public void postTweet(int userId, int tweetId) {}

    /** 返回该 user 关注的人（包括他自己）最近的动态 id，
     最多 10 条，而且这些动态必须按从新到旧的时间线顺序排列。*/
    public List<Integer> getNewsFeed(int userId) {}

    /** follower 关注 followee，如果 Id 不存在则新建 */
    public void follow(int followerId, int followeeId) {}

    /** follower 取关 followee，如果 Id 不存在则什么都不做 */
    public void unfollow(int followerId, int followeeId) {}
}

接下来是具体的四个API实现：

发一条推文：需要维护一个用户和所发推文列表的对应关系，用HashMap实现。新推文加入推文列表采用头插法，让最新的推文保持在表头，形成从新到旧的顺讯(时间戳从大到小)。

public void postTweet(int userId, int tweetId) {
    //全局时间自增
    timestamp++;
    //用户和推文列表映射存在则新增一条推文
    if (twitter.containsKey(userId)) {
        //头插法
        Tweet oldHead = twitter.get(userId);
        Tweet newHead=new Tweet(tweetId,timestamp);
        newHead.next=oldHead;
        twitter.put(userId,newHead);
    }else {
        twitter.put(userId,new Tweet(tweetId,timestamp));
    }
}

时间复杂度：O(1)

关注一个人方法、取关一个人方法：每个用户都有一个关注列表，用HashMap存储这个对应关系；关注列表不需要有序只需要唯一即可，为了存取方便选用HashSet实现；每个用户

/** follower 关注 followee，如果 Id 不存在则新建 */
public void follow(int followerId, int followeeId) {
    //不能关注自己
    if (followeeId==followerId)return;
    HashSet<Integer> set = followed.get(followerId);
    if (set == null) {
        HashSet init=new HashSet();
        init.add(followeeId);
        followed.put(followerId,init);
    }else {
        //已关注过
        if (set.contains(followeeId))return;
        set.add(followeeId);
    }
}

/** follower 取关 followee，如果 Id 不存在则什么都不做 */
public void unfollow(int followerId, int followeeId) {
    //不能取关自己
    if (followeeId==followerId)return;
    HashSet<Integer> set = followed.get(followerId);
    if (set == null) {
        return;
    }
    set.remove(followeeId);
}

时间复杂度：O(1)

返回关注的人最近的动态方法：到这里应该已经知道每个人都有自己一个链表作为推文列表(头插法最新的在前面)，我们要做的就是将这关注列表中的K个人的有序推文列表合并，获得前10个即可。

于是这个问题就转换为NO.23合并K个有序链表，只不过本题是降序而已。这里我们可以使用一个大顶堆，将所有关注用户(包括自己)的推文列表的头节点入堆，然后每次弹出堆顶节点node，放入结果集，如果node.next不为空将next入堆。

直至结果集中有十条推文时返回。

public List<Integer> getNewsFeed(int userId) {
    //因为堆是全局适用的，用之前要进行clear
    maxHeap.clear();
    //自己的推文也要记录
    if (twitter.containsKey(userId)) maxHeap.offer(twitter.get(userId));
    //将关注列表所有用户的推文列表头节点入堆
    HashSet<Integer> followedList = followed.get(userId);
    if (followedList != null && followedList.size() > 0) {
        for (Integer followedId : followedList) {
            Tweet tweet = twitter.get(followedId);
            if (tweet != null) {
                maxHeap.offer(tweet);
            }
        }
    }
    //取出十条最新的放入结果集
    List<Integer> res = new ArrayList<>();
    int count = 0;
    while (!maxHeap.isEmpty() && count < 10) {
        Tweet tweet = maxHeap.poll();
        res.add(tweet.id);
        count++;
        if (tweet.next != null) maxHeap.offer(tweet.next);
    }
    return res;
}

时间复杂度：O(nlogn) n是参数用户的关注数量，弹出堆顶O(1)，入堆调整O(logn)，最多入堆n次。

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.355 设计推特 中等

NO.355 设计推特中等