Leetcode.146 LRU 缓存
题目链接
Leetcode.146 LRU 缓存
mid
题目描述
请你设计并实现一个满足 LRU
(最近最少使用) 缓存 约束的数据结构。
实现 LRUCache
类:
LRUCache(int capacity)
以 正整数 作为容量 c a p a c i t y capacity capacity 初始化LRU
缓存int get(int key)
如果关键字 k e y key key 存在于缓存中,则返回关键字的值,否则返回 − 1 -1 −1 。void put(int key, int value)
如果关键字 k e y key key 已经存在,则变更其数据值 v a l u e value value ;如果不存在,则向缓存中插入该组 k e y − v a l u e key-value key−value 。如果插入操作导致关键字数量超过 c a p a c i t y capacity capacity ,则应该 逐出 最久未使用的关键字。
函数 g e t get get 和 p u t put put 必须以 O ( 1 ) O(1) O(1) 的平均时间复杂度运行。
示例:
输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]解释 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是
{1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1); // 返回
1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1
作废,缓存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3);
// 返回 3 lRUCache.get(4); // 返回 4
提示:
- 1 ≤ c a p a c i t y ≤ 3000 1 \leq capacity \leq 3000 1≤capacity≤3000
- 0 ≤ k e y ≤ 10000 0 \leq key \leq 10000 0≤key≤10000
- 0 ≤ v a l u e ≤ 1 0 5 0 \leq value \leq 10^5 0≤value≤105
- 最多调用 2 ∗ 1 0 5 2 * 10^5 2∗105 次 g e t get get 和 p u t put put
解法:双向链表 + 哈希表
我们先设计出双向链表的节点 Node
:
struct Node{Node* prev;Node* next;int key;int val;Node(int k,int v){key = k;val = v;prev = nullptr;next = nullptr;}
};
我们开始设计链表的 API。
struct LinkedList{Node* head; //链表头节点(假)Node* tail; //链表尾节点(假)unordered_map<int,Node*> mp; //根据键值 key 获得对应的节点 nodeint size; //节点数量 , 初始为0int capacity; //链表容量,即链表最多能由几个节点,多了的节点就移除
};
每次我们通过 g e t get get 和 p u t put put 操作节点之后,我们就要将其移动到链表头部,所以我们需要一个节点 node
插入到链表头部的函数 add
:
void add(Node* node){head->next->prev = node;node->next = head->next;head->next = node;node->prev = head;
}
此外,我们需要从链表中删除指定节点 node
:
void remove(Node* node){node->prev->next = node->next;node->next->prev = node->prev;
}
当链表中的节点数量 s i z e size size 超过链表容量 c a p a c i t y capacity capacity 时 ,即 s i z e > c a p a c i t y size > capacity size>capacity。我们就需要移除尾部的节点 并且 从 m p mp mp 删除对应的 k e y key key 和 n o d e node node 的关系:
void remove(){Node* node = tail->prev; //要删除的是尾部的节点remove(node);int key = node->key;mp.erase(key);size--; //移除节点,链表节点数量 - 1
}
对于 g e t get get,如果不存在 k e y key key 对应的节点,直接返回 − 1 -1 −1;如果存在 ,返回对应节点 n o d e node node 的值,并且将 n o d e node node 提升到链表头部:
int get(int key){if(!mp.count(key)) return -1;Node* node = mp[key];int ans = node->val;//如果此时 node 已经是第一个节点了,就没必要移动了,直接返回node->valif(node == head->next) return ans;//将 node 移动到链表头部remove(node);add(node);return ans;
}
对于 p u t put put,如果存在 k e y key key 对应的节点,我们更新节点值,然后将节点移动到头部即可;如果不存在,那我们直接插入新的节点 N o d e ( k e y , v a l u e ) Node(key,value) Node(key,value),如果此时超出容量,还要移除尾部的节点:
void put(int key,int value){if(mp.count(key)){Node* node = mp[key];node->val = value;if(node == head->next) return;remove(node);add(node);return;}Node* node = new Node(key,value);mp[key] = node;add(node);size++;if(size > capacity) remove();
}
时间复杂度: O ( 1 ) O(1) O(1)
完整代码:
struct Node{Node* prev;Node* next;int key;int val;Node(int k,int v){key = k;val = v;prev = nullptr;next = nullptr;}
};struct LinkedList{Node* head;Node* tail;unordered_map<int,Node*> mp;int size;int capacity;LinkedList(int c){head = new Node(-1,-1);tail = new Node(-1,-1);head->next = tail;tail->prev = head;size = 0;capacity = c;}void put(int key,int value){if(mp.count(key)){Node* node = mp[key];node->val = value;if(node == head->next) return;remove(node);add(node);return;}Node* node = new Node(key,value);mp[key] = node;add(node);size++;if(size > capacity) remove();}int get(int key){if(!mp.count(key)) return -1;Node* node = mp[key];int ans = node->val;if(node == head->next) return ans;remove(node);add(node);return ans;}void add(Node* node){head->next->prev = node;node->next = head->next;head->next = node;node->prev = head;}void remove(){Node* node = tail->prev;remove(node);int key = node->key;mp.erase(key);size--;}void remove(Node* node){node->prev->next = node->next;node->next->prev = node->prev;}
};class LRUCache {
public:LinkedList* list;LRUCache(int capacity) {list = new LinkedList(capacity);}int get(int key) {return list->get(key);}void put(int key, int value) {list->put(key,value);}
};/*** Your LRUCache object will be instantiated and called as such:* LRUCache* obj = new LRUCache(capacity);* int param_1 = obj->get(key);* obj->put(key,value);*/
相关文章:
Leetcode.146 LRU 缓存
题目链接 Leetcode.146 LRU 缓存 mid 题目描述 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类: LRUCache(int capacity) 以 正整数 作为容量 c a p a c i t y capacity capacity 初始化 LRU 缓存int get(int key) 如果关键…...
科技资讯|Canalys发布全球可穿戴腕带设备报告,智能可穿戴增长将持续
市场调查机构 Canalys 近日发布报告,表示 2023 年第 2 季度全球可穿戴腕带设备出货量达 4400 万台,同比增长了 6%。 主要归功于其亲民的价格以及消费者对价位较高的替代品仍持谨慎态度,基础手环市场尽管与去年同期相比有所下降,…...
使用https接口,无法调通接口响应不安全
网页pc使用不安全https 页面提示不安全–点击高级–跳过 接口使用部安全https 无法像页面一样可以跳过 方法:安装证书 还是无法响应报错不安全: 1、确定证书绑定ip还是域名(ip和域名都可以绑定) 使用的是httpsip,报…...
uniapp开发h5,解决项目启动时,Network: unavailable问题
网上搜了很多,发现都说是要禁用掉电脑多余的网卡,这方法我试了没有好,不晓得为啥子,之后在网上看,uniapp的devServer vue2的话对标的就是webpack4的devserver(除了复杂的函数配置项),…...
9.17 校招 实习 内推 面经
绿泡*泡: neituijunsir 交流裙 ,内推/实习/校招汇总表格 1、自动驾驶一周资讯 - 一汽与Mobileye 签署战略合作,小鹏汽车将用经销商销售逐渐替换直营模式,原小鹏汽车副总裁加盟赛力斯 自动驾驶一周资讯 - 一汽与Mobileye 签署战…...
【Python小项目之Tkinter应用】随机点名/抽奖工具大优化:新增查看历史记录窗口!语音播报功能!修复预览文件按钮等之前版本的bug!
文章目录 前言一、实现思路二、关键代码查看历史记录按钮语音播报按钮三、完整代码总结前言 老生常谈,先看效果:(订阅专栏可获取完整代码) 初始状态下,我们为除了【设置】外的按钮添加弹窗,提示用户在使用工具之前要先【设置】。在设置界面,我们主要修改了【预览文件】…...
数据结构与算法:排序算法(1)
目录 冒泡排序 思想 代码实现 优化 鸡尾酒排序 优缺点 适用场景 快速排序 介绍 流程 基准元素选择 元素交换 1.双边循环法 使用流程 代码实现 2.单边循环法 使用流程 代码实现 3.非递归实现 排序在生活中无处不在,看似简单,背后却隐藏…...
NotePad++ 在行前/行后添加特殊字符内容方法
我们在处理数据时,会遇到需要在每行数据前面、后面、开头、结尾添加各种不一样的字符 如果数据不多,我们可以自己手动的去添加,但如果达到了成百上千行,此时再机械的手动添加是不现实的 这里教给大家如何快速的在数据每行的前后…...
【JavaEE】多线程案例-线程池
文章目录 1. 什么是线程池2. 为什么要使用线程池(线程池有什么优点)3. 如何使用Java标准库提供的线程池3.1 创建一个线程池对象3.2 什么是工厂模式3.3 为什么要使用工厂模式3.4 Executors 创建不同具有不同特性的线程池3.5 ThreadPool 类的构造方法3.6 线…...
服务器搭建(TCP套接字)-fork版(服务端)
基础版的服务端虽然基本实现了服务器的基本功能,但是如果客户端的并发量比较大的话,服务端的压力和性能就会大打折扣,为了提升服务端的并发性能,可以通过fork子进程的方式,为每一个连接成功的客户端fork一个子进程,这样…...
缺失的第一个正数:高效解法与技术
缺失的第一个正数:高效解法与技术 背景 在计算机编程中,有时候需要寻找一个未排序整数数组中没有出现的最小的正整数。这篇技术博客将详细讨论这个问题,并提供一个时间复杂度为 O(n) 且只使用常数级别额外空间的解决方案。 问题描述 leet…...
常用的辅助网站(持续更新)
标题 一、uni-app方向二、H5方向 一、uni-app方向 1、uni-app官网 地址:https://uniapp.dcloud.net.cn/ 2、香蕉云编 地址:https://www.yunedit.com/ 描述:一般用来配置ios证书或安卓证书、上传ios包至商店 3、uView 地址:http…...
LeetCode 75 - 01 : 最小面积矩形
type pair struct{x, y int }func minAreaRect(points [][]int)int{mp : map[pair]struct{}{}// 将二维数组中的坐标映射到map中for i : range points{mp[pair{points[i][0], points[i][1]}] struct{}{}}// 将结果设置为一个最大值,防止影响求最小值的逻辑res : ma…...
每日一题:请解释什么是闭包(Closure)?并举一个实际的例子来说明。(前端初级)
今天继续在前端初级笔试题中被AI虐: 碱面的答案,问题:初级,回答:初级https://bs.rongapi.cn/1702510598371151872/14我的回答如下: 闭包是指由大括号包裹的一个区域,这个区域代表了一个变量生效…...
广告主必看!NetMarvel五大优势驱动出海App投放增长
App出海走到今天,流量红利早就不存在,摆在广告主面前最棘手的两个问题,一是不起量,二是买量成本太高,得不偿失。 如何在确保出海应用用户规模有所增长的同时,也保证整体ROI处在较高水平?NetMar…...
数据结构与算法之复杂度
时间复杂度 1.抓大头 2.常数用o(1),低阶函数也用o(1)代替(直接去掉) 3.取最坏情况 对数相关写法的规定...
ATECLOUD电源测试软件平台如何测试电源纹波?
电源纹波是影响电源稳定性的重要因素,过大的纹波会导致电源模块的工作效率降低,可能使电源模块直接损坏。使用ATECLOUD碘盐测试软件平台对纹波进行测试,检测其工作情况,以确保其稳定性和性能。 电源纹波的产生 电源的纹波通俗的来…...
数据结构与算法:排序算法(2)
目录 堆排序 使用步骤 代码实现 计数排序 适用范围 过程 代码实现 排序优化 桶排序 工作原理 代码实现 堆排序 二叉堆的特性: 1. 最大堆的堆顶是整个堆中的最大元素 2. 最小堆的堆顶是整个堆中的最小元素 以最大堆为例,如果删除一个最大堆的…...
1_图神经网络GNN基础知识学习
文章目录 安装PyTorch Geometric安装工具包 在KarateClub数据集上使用图卷积网络 (GCN) 进行节点分类两个画图函数Graph Neural Networks数据集:Zacharys karate club network.PyTorch Geometric数据集介绍 edge_index使用networkx可视化展示 Graph Neural Networks…...
瑞芯微:基于RK3568的ocr识别
光学字符识别(Optical Character Recognition, OCR)是指对文本资料的图像文件进行分析识别处理,获取文字及版面信息的过程。亦即将图像中的文字进行识别,并以文本的形式返回。OCR的应用场景 卡片证件识别类:大陆、港澳…...
C++真的是 C加加
📝个人主页:夏目浅石. 📌博客专栏:C的故事 🏠学习社区:夏目友人帐. 文章目录 前言Ⅰ. 函数重载0x00 重载规则0x01 函数重载的原理名字修饰 Ⅱ. 引用0x00 引用的概念0x01 引用和指针区分0x03 引用的本质0x04…...
java学习--day5 (java中的方法、break/continue关键字)
文章目录 day4作业今天的内容1.方法【重点】1.1为什么要有方法1.2其实已经见过方法1.3定义方法的语法格式1.3.1无参无返回值的方法1.3.2有参无返回值的方法1.3.3无参有返回值的方法1.3.4有参有返回值的方法 2.break和continue关键字2.1break;2.2continue; 3.案例关于方法的练习…...
MFC主框架和视类PreCreateWindow()函数学习
在VC生成的单文档应用程序中,主框架类和视类均具有PreCreateWindow函数; 从名字可知,可在此函数中添加一些代码,来控制窗口显示后的效果; 并且它有注释说明, Modify the Window class or styles here by…...
for forin forof forEach map区别
一、总结 相同点:都是串行遍历。不同点: 二、for of循环 设计目的:遍历所有数据结构的统一方法。原理:会调用数据结构的Symbol.iterator方法。 只要数据结构定义了Symbol.iterator属性,就能用for of遍历它的成员。…...
特殊时间(蓝桥杯)
特殊时间 问题描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 2022年2月22日22:20 是一个很有意义的时间, 年份为 2022 , 由 3 个 2 和 1 个 0 组成, 如果将月和日写成 4 位, 为 0222 , 也是由 3 个 2 和 1 个 0 组 成…...
VUE路由与nodeJS环境搭建
VUE路由 Vue路由是Vue.js提供的路由管理工具,它允许我们在应用程序中实现页面之间的导航,从而使单页面应用程序的开发更加方便。通过Vue路由,我们可以轻松地创建和管理多个视图,并在这些视图之间导航。 Vue路由使用HTML5的Histo…...
抗锯齿的线
抗锯齿的线 右下角的时候h是0,到顶部 h是1,然后中间y相距4个像素,那dy就是0.25 如果让h abs(fract(h - 0.5) - 0.5) 中间一行0.5,第一行 第三行都是0.25,两端都是0 根据插值来看 这里是 如果用h/dy 那么第一行以上࿰…...
如何使用高压放大器驱动高容性负载
使用高压放大器驱动高容性负载是一个具有挑战性的任务,需要仔细考虑电路设计和操作技巧。下面西安安泰Aigtek将为您介绍一些关于如何使用高压放大器驱动高容性负载的方法和注意事项。 首先,让我们了解一下高容性负载。高容性负载通常指电容值较大的负载元…...
kubernetes集群证书过期启动失败问题解决方法
1、问题现象 执行kubectl命令异常报告 [rootk8s-master1 ~]# kubectl get node The connection to the server 192.168.227.131:6443 was refused - did you specify the right host or port? [rootk8s-master1 ~]# 查看etcd的日志,报错信息如下 {"level&…...
nvm使用的注意事项和常用命令。
nvm官网下载地址:nvm文档手册 - nvm是一个nodejs版本管理工具 - nvm中文网 (uihtm.com) 参考网址:(14 封私信 / 80 条消息) 如何通过 nvm 安装多版本 nodejs?npm 安装失败了怎么办? - 知乎 (zhihu.com) nvm目录下,修…...
网站开发及代运营/2023年8月新冠
新电脑安装git,官网下载太慢,一个小时。以前没感觉啊。 网上教程很多,复制官网用迅雷,嗯,没冲会员就给你99%停下来。 360浏览器?安全绿色下载,导向中关村,上个月把我的新电脑整死了…...
商务网站规划设计要点/品牌策划方案模板
转载自http://cnlearn.linksprite.com/?p5248#.VwZrzvl95hE 数字 I/O (1)pinMode(pin, mode) 数字IO 口输入输出模式定义函数,pin 表示为0~13, mode 表示为INPUT 或OUTPUT 。(2) digitalWrite(…...
深圳哪里有网站建设/产品代理推广方案
题目:https://www.luogu.org/problemnew/show/P3205 同 关路灯,精髓在于左端点和右端点。 注意!!!L2时有重复! #include<iostream> #include<cstdio> using namespace std; int n,h[1005]; lon…...
湖南网站建设/各城市首轮感染高峰期预测
Swift标准库可以编译安卓armv7的内核,这使得可以在安卓移动设备上执行Swift语句代码。本文解释了如何在你的安卓手机上运行一个简单的“hello,world”程序。如果你遇到了任何问题,请参考下面的说明,上传BUG到 https://bugs.swift.…...
垂直型b2c网站有哪些/网络软营销
文章目录一、引言1.1 数据库压力过大1.2 数据不同步1.3 传统锁失效二、Redis介绍2.1 NoSQL介绍2.2 Redis介绍三、Redis安装3.1 安装Redis3.2 使用redis-cli连接Redis3.3 使用图形化界面连接Redis四、Redis常用命令【重点】4.1 Redis存储数据的结构4.2 string常用命令4.3 hash常…...
企业网站建设报价表/广告联盟代理平台
【目录】 一、【基础知识——扫盲】 二、【DOM、SAX、JDOM、DOM4j简单使用介绍】 三、【性能测试】 四、【对比】 五、【小插曲XPath】 六、【补充】 关键字:Java解析xml、解析xml四种方法、DOM、SAX、JDOM、DOM4j、XPath 【引言】 目前在Java中用于解析XML的技术很…...