LeetCode题练习与总结：设计推特--355

一、题目描述

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

实现 Twitter 类：

• Twitter() 初始化简易版推特对象
• void postTweet(int userId, int tweetId) 根据给定的 tweetId 和 userId 创建一条新推文。每次调用此函数都会使用一个不同的 tweetId 。
• List 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 的用户。

示例：

输入
["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"]
[[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]
输出
[null, null, [5], null, null, [6, 5], null, [5]]

解释
Twitter twitter = new Twitter();
twitter.postTweet(1, 5); // 用户 1 发送了一条新推文 (用户 id = 1, 推文 id = 5)
twitter.getNewsFeed(1);  // 用户 1 的获取推文应当返回一个列表，其中包含一个 id 为 5 的推文
twitter.follow(1, 2);    // 用户 1 关注了用户 2
twitter.postTweet(2, 6); // 用户 2 发送了一个新推文 (推文 id = 6)
twitter.getNewsFeed(1);  // 用户 1 的获取推文应当返回一个列表，其中包含两个推文，id 分别为 -> [6, 5] 。推文 id 6 应当在推文 id 5 之前，因为它是在 5 之后发送的
twitter.unfollow(1, 2);  // 用户 1 取消关注了用户 2
twitter.getNewsFeed(1);  // 用户 1 获取推文应当返回一个列表，其中包含一个 id 为 5 的推文。因为用户 1 已经不再关注用户 2

提示：

• 1 <= userId, followerId, followeeId <= 500
• 0 <= tweetId <= 10^4
• 所有推特的 ID 都互不相同
• postTweet、getNewsFeed、follow 和 unfollow 方法最多调用 3 * 10^4 次

二、解题思路

1. 使用一个数据结构来存储推文，可以使用列表或链表，列表中的每个元素代表一条推文，包含推文ID和用户ID。考虑到需要频繁地在头部插入新推文，使用链表结构更合适。

2. 使用一个哈希表来存储用户关注关系，键为用户ID，值为该用户关注的所有用户ID集合。

3. postTweet 方法：在推文链表的头部插入一条新推文。

4. getNewsFeed 方法：遍历推文链表，找出当前用户和其关注用户的推文，按时间顺序排序，取前10条推文。

5. follow 方法：在关注关系的哈希表中，将关注者ID添加到被关注者的关注者集合中。

6. unfollow 方法：在关注关系的哈希表中，将关注者ID从被关注者的关注者集合中移除。

三、具体代码

import java.util.*;
 
public class Twitter {
 
    private static class Tweet {
        int time;
        int tweetId;
        Tweet next;
 
        public Tweet(int time, int tweetId) {
            this.time = time;
            this.tweetId = tweetId;
            this.next = null;
        }
    }
 
    private Map> follows;
    private Map tweets;
    private int timeStamp;
 
    public Twitter() {
        follows = new HashMap<>();
        tweets = new HashMap<>();
        timeStamp = 0;
    }
 
    public void postTweet(int userId, int tweetId) {
        Tweet newTweet = new Tweet(timeStamp++, tweetId);
        newTweet.next = tweets.get(userId);
        tweets.put(userId, newTweet);
    }
 
    public List getNewsFeed(int userId) {
        List list = new ArrayList<>();
        // 添加当前用户的推文
        if (tweets.containsKey(userId)) {
            list.add(tweets.get(userId));
        }
        // 添加关注用户的推文
        if (follows.containsKey(userId)) {
            for (int followeeId : follows.get(userId)) {
                if (tweets.containsKey(followeeId)) {
                    list.add(tweets.get(followeeId));
                }
            }
        }
        // 按时间排序
        list.sort((a, b) -> b.time - a.time);
        List res = new ArrayList<>();
        for (Tweet tweet : list) {
            while (tweet != null && res.size() < 10) {
                res.add(tweet.tweetId);
                tweet = tweet.next;
            }
        }
        return res;
    }
 
    public void follow(int followerId, int followeeId) {
        follows.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
    }
 
    public void unfollow(int followerId, int followeeId) {
        if (follows.containsKey(followerId)) {
            follows.get(followerId).remove(followeeId);
        }
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

• Twitter 构造函数：

  • 初始化数据结构，时间复杂度为O(1)。

• postTweet 方法：

  • 每次调用时，直接在哈希表中插入新的推文节点，时间复杂度为O(1)。

• getNewsFeed 方法：

  • 遍历所有关注者的推文，最坏情况下，如果用户关注了所有其他用户，时间复杂度为O(N)，其中N是用户数量。
  • 将所有推文节点加入列表，时间复杂度为O(N)。
  • 对推文列表进行排序，时间复杂度为O(MlogM)，其中M是推文总数。
  • 遍历排序后的推文列表以获取前10条推文，最坏情况下时间复杂度为O(M)。
  • 综合起来，getNewsFeed的时间复杂度为O(N + MlogM + M)。

• follow 方法：

  • 在哈希表中添加关注关系，时间复杂度为O(1)。

• unfollow 方法：

  • 在哈希表中移除关注关系，时间复杂度为O(1)。

2. 空间复杂度

• Twitter 构造函数：

  • 初始化了两个哈希表和一个整数，空间复杂度为O(N)，其中N是用户数量。

• postTweet 方法：

  • 每次调用时，创建一个新的推文节点，空间复杂度为O(1)。

• getNewsFeed 方法：

  • 创建了一个推文列表，最坏情况下，列表的大小为所有用户推文的总数M，空间复杂度为O(M)。

• follow 方法：

  • 在哈希表中添加关注关系，空间复杂度为O(1)。

• unfollow 方法：

  • 移除哈希表中的关注关系，空间复杂度为O(1)。

总体空间复杂度：

• follows 哈希表存储了所有用户的关注关系，空间复杂度为O(N^2)。
• tweets 哈希表存储了所有用户的推文，空间复杂度为O(M)。
• 因此，总体空间复杂度为O(N^2 + M)。

综上所述，该Twitter类的时间复杂度和空间复杂度分别为O(N + MlogM + M)和O(N^2 + M)。

五、总结知识点

• 静态内部类：

  • Tweet 类被定义为 Twitter 类的静态内部类，用于表示一条推文，包含时间戳、推文ID和指向下一条推文的引用。

• 数据结构：

  • 使用了 HashMap 和 HashSet 来存储用户关注关系和用户的推文链表。
  • Tweet 类形成了一个单向链表，用于存储用户的所有推文。

• 时间戳：

  • 使用一个整数 timeStamp 作为全局时间戳，每次发推时递增，用于确定推文的顺序。

• 构造函数：

  • Twitter 类的构造函数初始化了两个哈希表 follows 和 tweets，以及时间戳 timeStamp。

• 方法重载：

  • postTweet、getNewsFeed、follow 和 unfollow 方法是 Twitter 类的成员方法，用于实现推文发布、获取新闻源、关注和取消关注的功能。

• 链表操作：

  • 在 postTweet 方法中，通过修改链表的头节点来添加新的推文。
  • 在 getNewsFeed 方法中，通过遍历链表来收集推文ID。

• 集合操作：

  • 使用 HashMap 的 computeIfAbsent 方法来安全地添加关注关系，避免空指针异常。
  • 使用 HashSet 的 add 和 remove 方法来管理关注列表。

• 排序算法：

  • 在 getNewsFeed 方法中，使用 List 的 sort 方法结合自定义比较器来对推文按时间戳降序排序。

• 迭代器使用：

  • 在 getNewsFeed 方法中，使用迭代器遍历推文链表，并收集推文ID。

• 条件判断：

  • 在 getNewsFeed、follow 和 unfollow 方法中，使用了条件判断来处理边界情况和异常情况。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。