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

embedded/2024/11/16 19:50:21/

一、题目描述

设计一个简化版的推特(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 的用户。

示例:

输入
["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 都互不相同
  • postTweetgetNewsFeedfollow 和 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<Integer, Set<Integer>> follows;private Map<Integer, Tweet> 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<Integer> getNewsFeed(int userId) {List<Tweet> 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<Integer> 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
  • 方法重载

    • postTweetgetNewsFeedfollow 和 unfollow 方法是 Twitter 类的成员方法,用于实现推文发布、获取新闻源、关注和取消关注的功能。
  • 链表操作

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

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

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

    • 在 getNewsFeed 方法中,使用迭代器遍历推文链表,并收集推文ID。
  • 条件判断

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

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


http://www.ppmy.cn/embedded/138087.html

相关文章

SpringBoot+Vue3开发会议管理系统

1 项目介绍 会议管理系统&#xff0c;简化公司内会议方面的流程&#xff0c;提供便捷。实现对会议室的管理、会议的管理、会议预约的管理&#xff0c;三大主流程模块。 系统分为三种角色&#xff0c;分别是员工、管理员和超级管理员。 员工角色功能&#xff1a;查看会议室占…

【HarmonyOS】鸿蒙应用低功耗蓝牙BLE的使用心得 (三)

【HarmonyOS】鸿蒙应用低功耗蓝牙BLE的使用心得 &#xff08;三&#xff09; 一、前言 目前鸿蒙最新系统&#xff0c;经过测试还有两个BLE相关Bug正在修复&#xff1a; 1.获取本地设备蓝牙名称&#xff0c;会为空&#xff0c;只有点击到设置蓝牙中查看后&#xff0c;该接口才能…

基于matlab的CNN食物识别分类系统,matlab深度学习分类,训练+数据集+界面

文章目录 前言&#x1f393;一、数据集准备&#x1f393;二、模型训练&#x1f340;&#x1f340;1.初始化&#x1f340;&#x1f340;2.加载数据集&#x1f340;&#x1f340;3.划分数据集&#xff0c;并保存到新的文件夹&#x1f340;&#x1f340;4.可视化数据集&#x1f34…

Keil基于ARM Compiler 5的工程迁移为ARM Compiler 6的工程

环境&#xff1a; keil版本为5.38&#xff0c;版本务必高于5.30 STM32F4的pack包版本要高于2.9 软件包下载地址&#xff1a;https://zhuanlan.zhihu.com/p/262507061 一、更改Keil中编译器 更改后编译&#xff0c;会报很多错&#xff0c;先不管。 二、更改头文件依赖 观察…

LuaRocks如何安装数据库驱动?

大家好&#xff0c;我是袁庭新。通过LuaRocks来安装数据库驱动如何实现呢&#xff1f;这篇文章帮你搞定。 LuaSQL是从Lua到DBMS的简单接口。LuaSQL它使Lua程序能够&#xff1a; 连接到ODBC、ADO、Oracle、MySQL、SQLite、Firebird和PostgreSQL数据库&#xff1b; 执行任意的S…

【免越狱】iOS砸壳 可下载AppStore任意版本 旧版本IPA下载

软件介绍 下载iOS旧版应用&#xff0c;简化繁琐的抓包流程。 一键生成去更新IPA&#xff08;手机安装后&#xff0c;去除App Store的更新检测&#xff09;。 软件界面 支持系统 Windows 10/Windows 8/Windows 7&#xff08;由于使用了Fiddler库&#xff0c;因此需要.Net环境…

[Qt platform plugin问题] Could not load the Qt platform plugin “xcb“

Qt platform plugin 是 Qt 应用程序启动时加载的插件。不同的平台有不同的插件。 常见的插件有:linuxfb Wayland xcb 简单来说就是启动一个GUI程序, 离不开这些插件.选择其中一个就好 出现这个问题要么就是没有插件&#xff0c;要么就是插件依赖的库没有。 要么就是插件选则的…

《配电网高质量发展行动实施方案(2024~2027年)》发布,智能巡检机器人助力新型电力系统建设

8月&#xff0c;国家能源局印发《配电网高质量发展行动实施方案&#xff08;2024~2027年&#xff09;》&#xff08;以下简称《方案》&#xff09;&#xff0c;深入推进配电网高质量发展重点任务落地见效。《方案》明确提出&#xff0c;要重点推进建设一批满足新型主体接入的项…