【C++】每日一题 146 LRU缓存

news/2024/5/30 2:05:50/文章来源:https://blog.csdn.net/ZSZ_shsf/article/details/136694428

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类:
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 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

336ms

typedef struct LRUnode{int key, value;struct LRUnode* prev;struct LRUnode* next;LRUnode():key(0),value(0),prev(NULL),next(NULL){};LRUnode(int key, int value):key(key),value(value),prev(NULL),next(NULL){};
}LRUnode;class LRUCache {
private:unordered_map<int,LRUnode*> m;LRUnode *head;LRUnode *tail;int size;int capacity;public:LRUCache(int capacity):capacity(capacity),size(0) {head = new LRUnode();tail = new LRUnode();head->next = tail;tail->prev = head;}int get(int key) {     int ret;auto it = m.find(key);if(it != m.end()){          ret = it->second->value;it->second->next->prev = it->second->prev;it->second->prev->next = it->second->next;it->second->next=head->next;it->second->prev = head;head->next->prev = it->second;head->next = it->second;}else{ret = -1;}return ret;}void put(int key, int value) { auto it = m.find(key);if(it!=m.end()){it->second->value = value;it->second->next->prev = it->second->prev;it->second->prev->next = it->second->next;it->second->next=head->next;it->second->prev = head;head->next->prev = it->second;head->next = it->second;}else{LRUnode *newNode = new LRUnode(key,value);m.insert(make_pair(key,newNode));newNode->next = head->next;head->next->prev = newNode;newNode->prev = head;head->next = newNode;size++;if(size>capacity){LRUnode *delNode = tail->prev;//tail->prev->prev = tail;tail->prev = tail->prev->prev;tail->prev->next = tail;size--;m.erase(delNode->key);delete delNode;}}}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1006337.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

拼图小游戏制作教程:用HTML5和JavaScript打造经典游戏

&#x1f31f; 前言 欢迎来到我的技术小宇宙&#xff01;&#x1f30c; 这里不仅是我记录技术点滴的后花园&#xff0c;也是我分享学习心得和项目经验的乐园。&#x1f4da; 无论你是技术小白还是资深大牛&#xff0c;这里总有一些内容能触动你的好奇心。&#x1f50d; &#x…

mysql中的非空间数据导入sqlserver中空间化

以下操作都在Navicat Premium 15软件中操作 1、mysql导出数据 以导出csv为例 不修改导出路径的话默认就是在桌面 设置编码UTF-8 这边还是默认,最好不要修改,如果文本识别符号为空,导入的时候可能字段会错乱 开始即可 2、导入sqlserver数据库中

通过Maven创建Web工程

通过Maven创建Web工程 方式一方式二 方式一 1.先创建一个Maven工程 2.把该Maven模块的pom文件里添加一个war 3.选中该Maven模块 点击项目架构 4.手动添加一个Web架构 方式二 1.也是new一个模块 但是直接配置好Web 2.这里就是我IDEA对Maven的设置 3.第一次创建 可能…

第六篇【传奇开心果系列】Python的自动化办公库技术点案例示例:大学生数据全方位分析挖掘经典案例

传奇开心果博文系列 系列博文目录Python的自动化办公库技术点案例示例系列 博文目录前言一、Pandas库全方位分析挖掘大学生数据能力介绍二、大学生学生成绩数据分析数据挖掘示例代码三、大学生选课数据分析数据挖掘示例代码四、大学生活动参与数据分析数据挖掘示例代码五、大学…

我用Coze给自己的服务号加了一个多功能的GPT服务机器人

我用Coze给自己的服务号加了一个多功能的GPT服务机器人&#xff0c;可以查新闻&#xff0c;交互式回答问题&#xff0c;查快递&#xff0c;画图画&#xff0c;联网回答问题 可以查快递 试用&#xff1a;搜索觉醒AI

Excel判断CD两列在EF两列的列表中是否存在

需求 需要将CD两列的ID和NAME组合起来&#xff0c;查询EF两列的ID和NAME组合起来的列表中是否存在&#xff1f; 比如&#xff0c;判断第二行的“123456ABC”在EF的第二行到第四行中是否存在&#xff0c;若存在则显示Y&#xff0c;不存在则显示N 实现的计算公式 IF(ISNUMBER…

软考72-上午题-【面向对象技术2-UML】-UML中的图3

一、状态图 1-1、状态图的定义 状态图&#xff0c;展现了一个状态机&#xff0c;由&#xff1a;状态、转换、事件和活动组成&#xff0c;是系统的动态视图。 活动(动作) 可以在状态内执行也可以在状态转换(迁移) 时执行。 状态图强调&#xff1a;行为的事件顺序。 1-2、状态图…

4G安卓核心板T310_紫光展锐平台方案

紫光展锐T310应用 DynamlQ架构 12nm 制程工艺&#xff0c;采用 1*Cortex-A753*Cortex-A55处理器&#xff0c;搭载Android11.0操作系统&#xff0c;主频最高达2.0GHz.此外&#xff0c;DynamlQ融入了AI神经网络技术&#xff0c;新增机器学习指令&#xff0c;让其在运算方面的机器…

BigDL-LLM 安装指南——在iGPU集成显卡下使用BigDL-LLM大模型库加速LLM

文章目录 iGPU是什么&#xff1f;一、环境准备1.1 Visual Studio 2022 Community 安装1.2 安装或更新最新版本的GPU驱动程序1.3 安装英特尔oneAPI工具包2024.0版本1.4 安装Anaconda 二、BigDL -LLM 安装2.1 创建虚拟环境2.2 激活虚拟环境2.3 安装bigdl-llm[xpu] 三、运行环境配…

centos命令history设置记录10000行

今天在操作服务器的时候&#xff0c;用history查看操作记录的时候&#xff0c;发现只能查看10条&#xff0c;这样不行啊&#xff0c;我想查看所有人对服务器操作的命令。 [rootbogon ~]# history解决办法&#xff1a; #1、找到/etc/profile文件中的histsize 把10改成10000 […

Netty架构详解

文章目录 概述整体结构Netty的核心组件逻辑架构BootStrap & ServerBootStrapChannelPipelineFuture、回调和 ChannelHandler选择器、事件和 EventLoopChannelHandler的各种ChannelInitializer类图 Protocol Support 协议支持层Transport Service 传输服务层Core 核心层模块…

打卡学习kubernetes——kubernetes架构原理

接上一篇的内容&#xff0c;除了核心组件&#xff0c;还有一些推荐的Add-ons&#xff1a; kube-dns 负责为整个集群提供DNS服务Ingress Controller 为服务提供外网入口Heapster 提供资源监控&#xff08;没用过这个&#xff0c;但是用过grafana&#xff0c;很方便&#xf…

【网络安全】手机不幸被远程监控,该如何破解,如何预防?

手机如果不幸被远程监控了&#xff0c;用三招就可以轻松破解&#xff0c;再用三招可以防范于未然。 三招可破解可解除手机被远程监控 1、恢复出厂设置 这一招是手机解决软件故障和系统故障的终极大招。只要点了恢复出厂设置&#xff0c;你手机里后装的各种APP全部将灰飞烟灭…

Ae 从入门到精通之三:合成与图层

图层 Layer是构建合成的基本单位。 一个图层上可以有一个或多个画面元素&#xff0c;多个图层在时间、空间上有组织地排列&#xff0c;从而创造丰富多彩的画面效果。 Ae 中的图层类似于 Ps 中的图层或 Pr 中的轨道。 合成 Composition是放置图层的“容器”。 每个合成都对应一个…

如何使用“Docker registry创建本地仓库,在服务器之间进行文件push和pull”?

1.1、在服务器1&#xff0c;运行registry docker run -d -p 5000:5000 -v ${PWD}/registry:/var/lib/registry --restart always --name registry registry:2.7.11.2、编辑/etc/docker/daemon.json 文件&#xff0c; 192.168.xxx.xxx 换成你自己 registry 服务的地址 sudo na…

vue 自定义组件绑定model+弹出选择支持上下按键选择

参考地址v-modelhttps://v2.cn.vuejs.org/v2/guide/components-custom-events.html#%E8%87%AA%E5%AE%9A%E4%B9%89%E7%BB%84%E4%BB%B6%E7%9A%84-v-model 原文代码 Vue.component(base-checkbox, {model: {prop: checked,event: change},props: {checked: Boolean},template: `…

通过日志恢复sql server数据库

在SQL Server中&#xff0c;通过日志恢复数据库是一个精细的过程&#xff0c;主要用于在数据库出现错误、数据丢失或需要回滚到特定时间点时恢复数据。以下是一般步骤概述&#xff1a; 设置恢复模式&#xff1a; 首先&#xff0c;数据库必须配置为“完整恢复模式”或“大容量…

Kubernetes专题-01 集群部署篇

kubernetes专题 注&#xff1a; 本教程由羞涩梦整理同步发布&#xff0c;本人技术分享站点&#xff1a;blog.hukanfa.com转发本文请备注原文链接&#xff0c;本文内容整理日期&#xff1a;2024-03-010csdn 博客名称&#xff1a;五维空间-影子&#xff0c;欢迎关注 1 集群规划…

【数据结构取经之路】快速排序及其优化

目录 简介 快速排序的实现步骤 快排的时间复杂度 快排的空间复杂度 霍尔法 证明 key > x left从key的位置出发的原因 霍尔法代码 (递归) 挖坑法 流程及其展开图 代码 (递归) 前后指针法 前后指针法的步骤及其动图 代码(递归) 快排的优化 一、三数取中 二、…

CentOS 7安装MySQL及常见问题与解决方案(含JDBC示例与错误处理)

引言 MySQL是一个流行的开源关系型数据库管理系统&#xff0c;广泛应用于各种业务场景。在CentOS 7上安装MySQL后&#xff0c;我们通常需要使用JDBC&#xff08;Java Database Connectivity&#xff09;连接MySQL进行后端操作。 目录 引言 CentOS 7安装MySQL 使用JDBC连接My…