当前位置: 首页 > news >正文

LeetCode 432. 全 O(1) 的数据结构

LeetCode 432. 全 O(1) 的数据结构

难度:hard\color{red}{hard}hard


题目描述

请你设计一个用于存储字符串计数的数据结构,并能够返回计数最小和最大的字符串。

实现 AllOneAllOneAllOne 类:

  • AllOne()AllOne()AllOne() 初始化数据结构的对象。
  • inc(Stringkey)inc(String key)inc(Stringkey) 字符串 keykeykey 的计数增加 111 。如果数据结构中尚不存在 keykeykey ,那么插入计数为 111keykeykey
  • dec(Stringkey)dec(String key)dec(Stringkey) 字符串 keykeykey 的计数减少 111 。如果 keykeykey 的计数在减少后为 000 ,那么需要将这个 keykeykey 从数据结构中删除。测试用例保证:在减少计数前,keykeykey 存在于数据结构中。
  • getMaxKey()getMaxKey()getMaxKey() 返回任意一个计数最大的字符串。如果没有元素存在,返回一个空字符串 """"""
  • getMinKey()getMinKey()getMinKey() 返回任意一个计数最小的字符串。如果没有元素存在,返回一个空字符串 """"""

注意: 每个函数都应当满足 O(1)O(1)O(1) 平均时间复杂度。

示例:

输入
["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
[[], ["hello"], ["hello"], [], [], ["leet"], [], []]
输出
[null, null, null, "hello", "hello", null, "hello", "leet"]解释
AllOne allOne = new AllOne();
allOne.inc("hello");
allOne.inc("hello");
allOne.getMaxKey(); // 返回 "hello"
allOne.getMinKey(); // 返回 "hello"
allOne.inc("leet");
allOne.getMaxKey(); // 返回 "hello"
allOne.getMinKey(); // 返回 "leet"

提示:

  • 1<=key.length<=101 <= key.length <= 101<=key.length<=10
  • keykeykey 由小写英文字母组成
  • 测试用例保证:在每次调用 decdecdec 时,数据结构中总存在 keykeykey
  • 最多调用 incincincdecdecdecgetMaxKeygetMaxKeygetMaxKeygetMinKeygetMinKeygetMinKey 方法 5∗1045 * 10^{4}5104

算法

(哈希表,双向链表)

  1. 定义结构体 Node,记录值 value 和所有等于该值的字符串集合。
  2. 维护一个哈希表,每个 key 对应的一个 Node 类型的指针。
  3. Node 结构按值的顺序组成双向链表。初始时有值为 INT_MIN 和值为 INT_MAX 的两个哨兵结点。
  4. 对于插入操作,如果哈希表中不存在,则在哈希表中添加 h[key] = new node(val)。从哈希表中取出当前结构体,将这个 key 添加到下一个结构体中(如果不存在则新建立结点),并在当前结构体中删除 key
  5. 对于删除,同理进行移动 key 的操作。
  6. 取最大最小值时,直接取链表的头或尾所对应的的字符串集合。

复杂度分析

  • 时间复杂度O(1)O(1)O(1)

  • 空间复杂度 : O(n)O(n)O(n)

C++ 代码

class AllOne {
public://创建一个双链表,其中有左右指针struct Node {Node *left, *right;int val;unordered_set<string> S;Node(int _val) {val = _val;left = right = NULL;}}*left, *right;// 创建一个哈希表unordered_map<string, Node*> hash;//初始化双链表最左边的节点和最右边的节点AllOne() {left = new Node(INT_MIN), right = new Node(INT_MAX);right->left = left, left->right = right;}//在节点的右边插入一个新的节点Node* add_to_right(Node *node, string key, int val) {if (node->right->val == val) node->right->S.insert(key);else {auto t = new Node(val);t->S.insert(key);t->right = node->right, node->right->left = t;node->right = t, t->left = node;}return node->right;}//在节点的左边边插入一个新的节点Node* add_to_left(Node *node, string key, int val) {if (node->left->val == val) node->left->S.insert(key);else {auto t = new Node(val);t->S.insert(key);t->left = node->left, node->left->right = t;node->left = t, t->right = node;}return node->left;}//删除一个节点void remove(Node* node) {node->left->right = node->right;node->right->left = node->left;delete node;}void inc(string key) {//如果该节点计数为0,在最左边插入一个值为1的节点if (hash.count(key) == 0) hash[key] = add_to_right(left, key, 1);else {//向右插入一个新的节点auto t = hash[key];t->S.erase(key);hash[key] = add_to_right(t, key, t->val + 1);if (t->S.empty()) remove(t);}}void dec(string key) {if (hash.count(key) == 0) return;auto t = hash[key];t->S.erase(key);if (t->val > 1) {hash[key] = add_to_left(t, key, t->val - 1);} else {hash.erase(key);}if (t->S.empty()) remove(t);}string getMaxKey() {if (right->left != left) return *right->left->S.begin();return "";}string getMinKey() {if (left->right != right) return *left->right->S.begin();return "";}
};/*** Your AllOne object will be instantiated and called as such:* AllOne* obj = new AllOne();* obj->inc(key);* obj->dec(key);* string param_3 = obj->getMaxKey();* string param_4 = obj->getMinKey();*/

修改变量版本:

class AllOne {
public:struct Node {Node *pre, *nxt;int value;unordered_set<string> keys;Node (int val) {value = val;pre = nxt = NULL;}}*left, *right;unordered_map<string, Node*> hash;AllOne() {left = new Node(0);right = new Node(INT_MAX);left->nxt = right;right->pre = left;}Node* add_to_right(Node* node, string key, int val) {if (node->nxt->value == val) node->nxt->keys.insert(key);else {auto t = new Node(val);t->keys.insert(key);t->nxt = node->nxt, node->nxt->pre = t;t->pre = node, node->nxt = t;}return node->nxt;}Node* add_to_left(Node* node, string key, int val) {if (node->pre->value == val) node->pre->keys.insert(key);else {auto t = new Node(val);t->keys.insert(key);node->pre->nxt = t, t->nxt = node;t->pre = node->pre, node->pre = t;}return node->pre;}void remove(Node *node) {node->pre->nxt = node->nxt;node->nxt->pre = node->pre;delete node;}void inc(string key) {if (hash.count(key) == 0) hash[key] = add_to_right(left, key, 1);else {auto t = hash[key];t->keys.erase(key);hash[key] = add_to_right(t, key, t->value + 1);if (t->keys.empty()) remove(t);}}void dec(string key) {if (hash.count(key) == 0) return;auto t = hash[key];t->keys.erase(key);if (t->value > 1) {hash[key] = add_to_left(t, key, t->value - 1);} else {hash.erase(key);}if (t->keys.empty()) remove(t);}string getMaxKey() {if (left->nxt != right) return *right->pre->keys.begin();return "";}string getMinKey() {if (right->pre != left) return *left->nxt->keys.begin();return "";}
};/*** Your AllOne object will be instantiated and called as such:* AllOne* obj = new AllOne();* obj->inc(key);* obj->dec(key);* string param_3 = obj->getMaxKey();* string param_4 = obj->getMinKey();*/

相关文章:

LeetCode 432. 全 O(1) 的数据结构

LeetCode 432. 全 O(1) 的数据结构 难度&#xff1a;hard\color{red}{hard}hard 题目描述 请你设计一个用于存储字符串计数的数据结构&#xff0c;并能够返回计数最小和最大的字符串。 实现 AllOneAllOneAllOne 类&#xff1a; AllOne()AllOne()AllOne() 初始化数据结构的对…...

再析jvm

前言 希望自己每一次学习都有不同的理解 文章目录前言1. jvm的组成取消永久代使用元空间原因2. 运行时数据区3. 堆栈区别队列和栈&#xff0c;队列先进先出&#xff0c;栈先进后出从栈顶弹出4. GC、内存溢出、垃圾回收4.1 如何确定引用是否会被回收4.1.1 Java中的引用类型4.1.…...

社招前端二面面试题总结

代码输出结果 var A {n: 4399}; var B function(){this.n 9999}; var C function(){var n 8888}; B.prototype A; C.prototype A; var b new B(); var c new C(); A.n console.log(b.n); console.log(c.n);输出结果&#xff1a;9999 4400 解析&#xff1a; conso…...

人人能读懂redux原理剖析

一、Redux是什么&#xff1f; 众所周知&#xff0c;Redux最早运用于React框架中&#xff0c;是一个全局状态管理器。Redux解决了在开发过程中数据无限层层传递而引发的一系列问题&#xff0c;因此我们有必要来了解一下Redux到底是如何实现的&#xff1f; 二、Redux的核心思想…...

uniCloud云开发----7、uniapp通过uni-swiper-dot实现轮播图

uniapp通过uni-swiper-dot实现轮播图前言效果图1、官网实现的效果2、需求中使用到的效果图官网提供的效果图源码1、html部分2、js部分3、css部分根据需求调整轮播图前言 uni-swiper-dot.文档 uni-swiper-dot 轮播图指示点 - DCloud 插件市场 本次展示根据需求制作的和官网用到…...

IM即时通讯构建企业协同生态链

在当今互联网信息飞速发展的时代&#xff0c;随着企业对协同办公要求的提高&#xff0c;协同办公的定义提升到了智能化办公的范畴。大多企业都非常重视构建连接用户、员工和合作伙伴的生态平台&#xff0c;利用即时通讯软件解决企业内部的工作沟通、信息传递和知识共享等问题。…...

Python实现构建gan模型, 输入一个矩阵和两个参数值,输出一个矩阵

构建一个GAN模型,使用Python实现,该模型将接受一个矩阵和两个参数值作为输入,并输出另一个矩阵。GAN(生成对抗网络)是一种深度学习模型,由生成器和判别器两部分组成,可以用于生成具有一定规律性的数据,如图像或音频。 # 定义生成器 def make_generator(noise_dim, dat…...

开学准备哪些电容笔?ipad触控笔推荐平价

在现代&#xff0c;数码产品的发展受到高技术的驱动。不管是在工作上&#xff0c;还是在学习上&#xff0c;大的显示屏可以使图像更加清晰。Ipad将成为我们日常生活中不可或缺的一部分&#xff0c;无论现在或将来。如果ipad配上一款方便操作的电容笔&#xff0c;将极大地提高我…...

放下和拿起 解放自己

放下太难&#xff0c;从过去中解放自己 工作这么久了&#xff0c;第一次不拿包上班&#xff0c;真爽 人的成长都是在碰撞和摸索中产生的&#xff0c;通过摸索&#xff0c;知道自己能力的边界和欲望的边界以及身体的边界&#xff0c;这三个决定了 你能做什么 你能享受什么&…...

100%BIM学员的疑惑:不会CAD可以学Revit吗?

在新一轮科技创新和产业变革中&#xff0c;信息化与建筑业的融合发展已成为建筑业发展的方向&#xff0c;将对建筑业发展带来战略性和全局性的影响。 建筑业是传统产业&#xff0c;推动建筑业科技创新&#xff0c;加快推进信息化发展&#xff0c;激发创新活力&#xff0c;培育…...

经常会采坑的javascript原型应试题

一&#xff0e; 前言 原型和原型链在面试中历来备受重视&#xff0c;经常被提及。说难可能也不太难&#xff0c;但要真正完全理解&#xff0c;吃透它&#xff0c;还是要多下功夫的。 下面为大家简单阐述我对原型和原型链的理解&#xff0c;若是觉得有说的不对的地方&#xff…...

完全背包—动态规划

一、背包问题概述 如图&#xff0c;完全背包与01背包的区别只有一点&#xff1a;01背包中每个物品只能取一个而完全背包中每个物品可以取无数个。解决完全背包问题必须首先弄明白01背包&#xff0c;不清楚的可以看我的这篇文章01背包—动态规划。 二、例题 重量价值物品0115物…...

消息队列MQ介绍

消息队列技术是分布式应用间交换信息的一种技术。消息队列可驻留在内存或磁盘上,队列存储消息直到它们被应用程序读走。通过消息队列&#xff0c;应用程序可独立地执行--它们不需要知道彼此的位置、或在继续执行前不需要等待接收程序接收此消息。 消息中间件概述 消息队列技术是…...

C语言进阶(八)—— 链表

1. 链表基本概念1.1 什么是链表链表是一种常用的数据结构&#xff0c;它通过指针将一些列数据结点&#xff0c;连接成一个数据链。相对于数组&#xff0c;链表具有更好的动态性&#xff08;非顺序存储&#xff09;。数据域用来存储数据&#xff0c;指针域用于建立与下一个结点的…...

手工测试用例就是自动化测试脚本——使用ruby 1.9新特性进行自动化脚本的编写

昨天因为要装watir-webdriver的原因将用了快一年的ruby1.8.6升级到了1.9。由于1.9是原生支持unicode编码&#xff0c;所以我们可以使用中文进行自动化脚本的编写工作。 做了简单的封装后&#xff0c;我们可以实现如下的自动化测试代码。请注意&#xff0c;这些代码是可以正确运…...

RockerMQ简介和单节点部署

目录一、RockerMQ简介二、Linux中单节点部署1、准备工作2、下载和解压3、修改初始内存4、启动5、查看进程6、发送接收消息测试7、关闭三、控制台的安装与启动(可视化页面)1、修改配置&#xff08;1&#xff09;修改端口号&#xff08;2&#xff09;指定RocketMQ的name server地…...

SFP光纤笼子 别称 作用 性能要点 工程要素

Hqst盈盛电子导读&#xff1a;2023年&#xff0c;Hqst盈盛电子于下属五金部开发生产SFP光纤连接器笼子等系列产品&#xff0c;所有产品生产及性标准都将参照连接器产品常用测试标准EIA-364-C等标准&#xff0c;以下为我司常规SFP光纤连接器基本性能要求SFP光纤笼子别称&#xf…...

[HarekazeCTF2019]Easy Notes

知识点&#xff1a;session 反序列化&#xff0c;代码审计代码分析 flag.php 中有个 is_admin 函数的判断。 在 lib.php 中有 is_admin 函数&#xff0c;需要 session[admin] 为 true&#xff0c;或者通过文件读取的方式。 在 index.php 中的 include 并不能使用伪协议读取 …...

Java学习-IO流-字符流-FileReader

Java学习-IO流-字符流-FileReader 字符流 字节流 字符集 输入流&#xff1a;默认一次读一个字节&#xff0c;遇到中文时一次读多个字节 输出流&#xff1a;底层把数据按照指定编码方式编码&#xff0c;变成字节写入文件 使用场景&#xff1a;纯文本文件读写 // …...

python攻陷米哈游《元神》数据?详情请看文章。。

前言 嗨喽&#xff0c;大家好呀~这里是爱看美女的茜茜呐 《原神》是由米哈游自研的一款全新开放世界冒险RPG。 里面拥有许多丰富得角色&#xff0c;让玩家为之着迷~ 今天&#xff0c;我们就来用python探索一下原神游戏角色信息&#xff01; 标题大家看看就好了哈~&#xff08…...

【unity细节】基于unity子对象(如相机)为什么无法进行z轴的拖拽移动和z轴自动归位的问题

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! 本文由 秩沅 原创 收录于专栏&#xff1a;unity细节和bug ⭐基于unity子对象为什么无法进行z轴的拖拽移动和z轴自动归位⭐ 文章目录⭐基于u…...

如何维护固态继电器?

固态继电器是SSR的简称&#xff0c;是由微电子电路、分立电子器件和电力电子功率器件组成的非接触式开关。隔离装置用于实现控制端子与负载终端之间的隔离。固态继电器的输入端使用微小的控制信号直接驱动大电流负载。那么&#xff0c;如何保养固态继电器呢&#xff1f; 在为小…...

Sprng依赖注入(三):构造方法注入是如何工作的?

前言这是Spring依赖注入系列的第三篇&#xff0c;前两篇主要分析了Spring bean依赖属性注入的两种方式&#xff0c;是字段注入和setter方法注入&#xff0c;单独比较这两种方式&#xff0c;会发现其过程和工作原理非常类似&#xff0c;那么构造方法注入会不会也和前两种比较类似…...

「1」指针进阶——详解

&#x1f680;&#x1f680;&#x1f680;大家觉不错的话&#xff0c;就恳求大家点点关注&#xff0c;点点小爱心&#xff0c;指点指点&#x1f680;&#x1f680;&#x1f680; 目录 &#x1f430;指针的回顾 &#x1f430;字符指针 &#x1f430;指针数组 &#x1f338;模…...

JS语法让人困惑的点 “==与===”

在JS中有很多神奇的语法&#xff0c;非常让人困惑&#xff0c;我们就先一一道来&#xff0c;相信你在开发中或多或少都踩过这些坑&#xff0c;或者让人无法理解。 今天我们就来说下【】和【】 这题对于很多没有系统学过前端开发的技术人员来说&#xff0c;算个重点&#xff0c…...

《狂飙》壁纸大嫂如此惊艳,做成日历壁纸天天看

兄弟们&#xff0c;今年的反腐大剧狂飙都有看吗 &#xff1f; 话说&#xff0c;名字虽然叫狂飙&#xff0c;但是全剧只有有田一个人在狂飙&#xff01; 当然&#xff0c;有田虽然亮眼&#xff0c;但是毕竟是个糟老头子&#xff0c;正经人谁看有田啊&#xff0c;当然是看大嫂了…...

手机照片删除了怎么恢复

手机照片删除了怎么恢复?喜欢拍照的小伙伴&#xff0c;都会不定期删除手机上的照片&#xff0c;因为这些爱拍照的人&#xff0c;手机中会存储着很多照片&#xff0c;删除照片是必然的&#xff0c;但在手机删除照片时&#xff0c;如果是一张一张删除太麻烦了&#xff0c;就直接…...

maven pom.xml 依赖的scope属性

maven pom.xml 依赖的scope属性 compile 适用范围 编译期、测试期、运行期 作用 从中央仓库拉取依赖到本地&#xff0c;并编译 打包到结果包中 runtime 适用范围 测试期、运行期 作用 runtime 用在 Class.forName(“com.mysql.jdbc.Driver”) 时&#xff0c;compile 编…...

git 的使用方法 (下 - 远程仓库和图形化)

目录前言&#xff1a;一、什么是协同开发二、Gitee 使用协同开发1. 首先注册一个码云账号2. 新建一个仓库3. 根据下图把新建仓库设置为开源4. 在远端合并分支的方法5. 链接 git 远程6. 提交&#xff08;同步&#xff09;远程7. 远程拉取至本地8. 远程分支三、git 图形化的使用1…...

Java基础:拼图小游戏

涉及到的知识: 1.图形用户接口GUI(Graphical User Interface)用图形化的方式显示操作界面 两个体系: AWT包和Swing包 2.界面会用到JFrame类 3.界面中的菜单会用到JMenuBar, JMenu, JMenuItem 4.添加图片 在设置完JLabel的location之后还需要获得展示内容的窗体, 通过setLay…...