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

一、题目描述

设计一个简化版的推特(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.xdnf.cn/news/8015.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

CodeQL学习笔记(4)-CodeQL for Java(程序元素)

最近在学习CodeQL&#xff0c;对于CodeQL就不介绍了&#xff0c;目前网上一搜一大把。本系列是学习CodeQL的个人学习笔记&#xff0c;根据个人知识库笔记修改整理而来的&#xff0c;分享出来共同学习。个人觉得QL的语法比较反人类&#xff0c;至少与目前主流的这些OOP语言相比&…

动态规划28:376. 摆动序列

动态规划解题步骤&#xff1a; 1.确定状态表示&#xff1a;dp[i]是什么 2.确定状态转移方程&#xff1a;dp[i]等于什么 3.初始化&#xff1a;确保状态转移方程不越界 4.确定填表顺序&#xff1a;根据状态转移方程即可确定填表顺序 5.确定返回值 题目链接&#xff1a;376.…

【zlm】h264 vp9 尝试研究

目录 编译与使用libvpx 打包lib 解决方案一 libvpx直接引用 IVF格式 编译libvpx windows下编译libvpx 参考文章 编译与使用libvpx 我们用最新的&#xff1a; x86_64-win64-vs16 最简单的视频编码器&#xff1a;编译&#xff08;libx264&#xff0c;libx265&#xff…

顺序表专题

目录 0. 什么是数据结构&#xff1f; 0. 为什么需要数据结构&#xff1f; 1.顺序表的概念及结构 2.顺序表分类&#xff1a; 3.动态顺序表的实现 4. 顺序表的应用 5. 顺序表的问题及思考 0. 什么是数据结构&#xff1f; 数据结构是由“数据”和“结构”两词结合而来 什…

关于使用svgIcon 菜单折叠 显示文字情况

使用的工具&#xff1a;vue2&#xff0c;ant design vue 问题&#xff1a; **解决&#xff1a;在<svg-icon> 外面包一层 <a-icon> ** 使用: 在 main.js 中&#xff1a;

【JAVA毕业设计】基于Vue和SpringBoot的师生健康管理系统

博主说明&#xff1a;本文项目编号 T 052 &#xff0c;文末自助获取源码 \color{red}{T052&#xff0c;文末自助获取源码} T052&#xff0c;文末自助获取源码 目录 一、系统介绍二、演示录屏三、启动教程四、功能截图五、文案资料5.1 选题背景5.2 国内外研究现状5.3 可行性分析…

双向链表专题

双向链表 1. 双向链表的定义和结构2. 双向链表的实现2.1 结构声明2.2 双向链表的初始化2.3 双向链表的打印2.4 尾插2.5 头插2.6 在指定位置之前插入2.7 在指定位置之后插入数据2.8 尾删2.9 头删2.10 删除指定位置的节点2.11 查找2.12 链表的销毁 3. 双向链表的细节 &#x1f52…

发票真伪查验方式-python数电票批量查验接口、发票ocr文字识别提取

在当今的商业环境中&#xff0c;确保交易的安全性和透明度是每个企业追求的目标。随着电子商务的迅猛发展&#xff0c;发票管理成为了企业财务管理中不可或缺的一环。面对海量的电子发票&#xff0c;企业财务也无需惊慌&#xff0c;翔云发票查验API接口&#xff0c;可以为企业提…

html+js+css实现拖拽式便签留言

前些日子在网上冲浪时&#xff0c;看到一个便签式留言墙&#xff0c;让人耳目一新。心想这个看着不错&#xff0c;额想要。于是便开始搜寻是否有相应开源插件&#xff0c;想将其引入自己的博客中。但是搜寻了一圈&#xff0c;都没有符合预期的,要么功能不符合。有的功能符合&am…

初识网络编程TCP/IP

目录 前言相关名词解释应用层协议——HTTP传输层协议socketTCP帧头格式三次握手、四次挥手 UDPTCP的socket实现 参考博文 前言 刚碰到网络编程&#xff0c;会出现一堆协议、概念、这层次那技术的&#xff0c;头都大了&#xff0c;还是得总结总结…… 相关名词解释 ✨✨网络…

Vue2进阶之Vue3高级用法

Vue3高级用法 响应式Vue2&#xff1a;Object.definePropertyObject.definePropertythis.$set设置响应式 Vue3&#xff1a;Proxy composition APIVue2 option API和Vue3 compositionAPIreactive和shallowReactivereadonly效果toRefs效果 生命周期main.jsindex.htmlLifeCycle.vue…

树叶分类竞赛(Baseline)以及kaggle的GPU使用

树叶分类竞赛(Baseline)-kaggle的GPU使用 文章目录 树叶分类竞赛(Baseline)-kaggle的GPU使用竞赛的步骤代码实现创建自定义dataset定义data_loader模型定义超参数训练模型预测和保存结果 kaggle使用 竞赛的步骤 本文来自于Neko Kiku提供的Baseline&#xff0c;感谢大佬提供代码…

与C语言的旅程之分支与循环(2)

与C语言的旅程之分支与循环 C语⾔是结构化的程序设计语⾔&#xff0c;这⾥的结构指的是顺序结构、选择结构、循环结构&#xff0c; 目录 与C语言的旅程之分支与循环 1. if语句 1.1 if ​编辑1.2 else 1.3 分⽀中包含多条语句 1.4 嵌套if 1.5 悬空else问题 2. 关系操作符…

springBoot 自动配置与starter

目录 一、自动配置 Springboot实现自动配置的核心机制 Conditional的作用是什么&#xff1f; 如何自定义自动配置&#xff1f; 步骤 例子分析 自动配置的优先级 如何禁用特定的自动配置&#xff1f; 二、starter 如何理解Spring Boot中的starter&#xff1f; 如何自…

《Python编程实训快速上手》第三天--字典和结构化数据

一、字典 1、字典数据类型介绍 myCat {"size":"fat","color":"gray"} 特征&#xff1a; 字典输入时带上{}字典中每一个值是以键值对形式存在&#xff0c;先写键&#xff0c;再写值 2、字典与列表 列表索引必须是整数&#xff0c;字…

Pinia小菠萝(状态管理器)

Pinia 是一个专为 Vue 3 设计的状态管理库&#xff0c;它借鉴了 Vuex 的一些概念&#xff0c;但更加轻量灵活。下面将详细介绍如何使用 Pinia 状态管理库&#xff1a; 安装 Pinia 使用 npm&#xff1a;在项目目录下运行npm install pinia。使用 yarn&#xff1a;在项目目录下运…

【智能算法应用】哈里斯鹰算法优化二维栅格路径规划问题

摘要 本文研究了基于哈里斯鹰优化算法&#xff08;Harris Hawks Optimization, HHO&#xff09;的二维栅格路径规划方法。HHO算法模拟哈里斯鹰的猎食行为&#xff0c;通过迭代搜索过程找到从起点到终点的最优路径&#xff0c;避开栅格中的障碍物。实验结果表明&#xff0c;HHO…

vue/react做多语言国际化的时候,在语言配置中不同的语言配置不同的字体,动态引入scss里面

如果想直接在vue文件的css里面使用&#xff0c;就可以使用i18n的t函数&#xff0c;注意t外层也有引号&#xff1a; font-size: v-bind("t(style.teamCurModelFontSize)"); 前提是要引入t函数&#xff1a;

优衣库在淘宝平台的全方位竞品分析与店铺表现研究:市场定位与竞争策略透视

优衣库品牌在淘宝平台的全方位竞品与店铺表现分析 一、品牌商品分析 1.商品列表与分类分析&#xff08;数据来源&#xff1a;关键词商品搜索接口&#xff1b;获取时间&#xff1a;2024.08.30&#xff09; 商品类别分布柱状图&#xff1a; 根据关键词商品搜索接口获取到的优衣…

spark新能源汽车推荐系统-计算机设计毕业源码42422

摘要 本论文致力于探讨基于Spark技术的新能源汽车推荐系统新能源汽车分析及可视化内容。系统将严格按照软件开发流程进行各个阶段的工作&#xff0c;利用Python编程语言中的爬虫功能&#xff0c;实现对懂车帝的汽车信息数据的爬取&#xff0c;作为系统的数据来源&#xff0c;并…