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

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

请你设计并实现一个满足 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;}}}
};

相关文章:

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

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类&#xff1a; LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中&#xff0c;则返回关键字的值&#xff0c;否则返回 -1 …...

CentOS搭建NAS服务器并使用

CentOS搭建NAS服务器并使用 文章目录 前言一、配置NAS服务器安装 NFS 服务&#xff1a;启动 NFS 服务&#xff1a;使 NFS 服务在系统启动时自动启动&#xff1a; 二、挂载服务器三、常见错误以及解决方案1、mount.nfs: No route to host2、mount.nfs: access denied by server …...

爬虫入门到精通_框架篇16(Scrapy框架基本使用)_名人名言的抓取

1 目标站点分析 抓取网站&#xff1a;http://quotes.toscrape.com/ 主要显示了一些名人名言&#xff0c;以及作者、标签等等信息&#xff1a; 点击next&#xff0c;page变为2&#xff1a; 2 流程框架 抓取第一页&#xff1a;请求第一页的URL并得到源代码&#xff0c;进行下…...

mac inter 芯片遇到程序无法打开(无法验证开发者)

mac inter 芯片遇到程序无法打开&#xff08;无法验证开发者&#xff09; 解决方案 终端运行命令&#xff1a; sudo xattr -r -d com.apple.quarantine 文件路径(直接把文件拖入到终端&#xff0c;可以自动找到文件路径)即可令其获得权限 补充知识&#xff1a; 通过gpt可以…...

科技成果鉴定测试如何进行?第三方检测机构进行鉴定测试的好处

科技成果鉴定测试&#xff0c;作为科技领域中一项重要的质量检验手段&#xff0c;具有广泛的应用范围。旨在为科技成果的研发者和使用者提供客观、科学、权威的鉴定结果&#xff0c;从而评估科技成果的技术水平和市场竞争力。   科技成果鉴定测试是对科技成果进行系统、全面的…...

八、词嵌入语言模型(Word Embedding)

词嵌入&#xff08;Word Embedding, WE&#xff09;&#xff0c;任务是把不可计算、非结构化的词转换为可以计算、结构化的向量&#xff0c;从而便于进行数学处理。 一个更官方一点的定义是&#xff1a;词嵌入是是指把一个维数为所有词的数量的高维空间&#xff08;one-hot形式…...

重学SpringBoot3-WebMvcConfigurer接口

摘要&#xff1a; 本文详细介绍了SpringBoot 3中的WebMvcConfigurer接口&#xff0c;旨在帮助读者深入理解其原理和实现&#xff0c;从而能够更好地使用SpringBoot进行Web开发。阅读本文需要大约30分钟。 关键词&#xff1a;SpringBoot, WebMvcConfigurer, SpringMVC, Web开发…...

《深入理解springCloud与微服务》笔记

第一章 微服务介绍 1.3 微服务的不足 1.3.2 分布式事务 CAP 理论&#xff0c;即同时满足“一致性”“可用性”和“分区容错”是 件不可能的事。 Consistency &#xff1a;指数据的强一致性。如果写入某个数据成功&#xff0c;之后读取&#xff0c;读到的都是新写入的数据&a…...

Vivado原语模板

1.原语的概念 原语是一种元件! FPGA原语是芯片制造商已经定义好的基本电路元件,是一系列组成逻辑电路的基本单元,FPGA开发者编写逻辑代码时可以调用原语进行底层构建。 2.原语的分类 原语可分为预定义原语和用户自定义原语。预定义原语为如and/or等门级原语不需要例化,可以…...

【linux本地安装tinycudann包教程】

【linux本地安装tinycudann包教程】 tiny-cuda-nn官网链接 如果你是windows 10系统的,想要安装tiny-cuda-nn可以参考我的文章——windows 10安装tiny-cuda-n包 根据官网要求:C++要求对应14,其实这样就已经告诉我们linux系统中的gcc版本不能高于9,同时下面又告诉我们gcc版…...

使用Nginx进行负载均衡

什么是负载均衡 Nginx是一个高性能的开源反向代理服务器&#xff0c;也可以用作负载均衡器。通过Nginx的负载均衡功能&#xff0c;可以将流量分发到多台后端服务器上&#xff0c;实现负载均衡&#xff0c;提高系统的性能、可用性和稳定性。 如下图所示&#xff1a; Nginx负…...

什么护眼台灯效果好?热门护眼台灯全方位测评推荐

台灯可以说是佳佳必备&#xff0c;尤其是家中有正在上学的孩子的更是需要一款好的台灯&#xff0c;不管是看书、写字都离不开台灯。不过很多家长在挑选台灯时往往仅关注到光线亮度是否充足&#xff0c;而忽略掉光线均匀度、舒适度等等方面的问题。所以选择一款优质的护眼台灯是…...

云上三问,迈向智能时代的关键

在今天的中国&#xff0c;第一热词是什么&#xff1f;面对这个问题&#xff0c;“新质生产力”当仁不让&#xff0c;而智能化技术毫无疑问是“新质生产力”最重要的来源之一。 在这样的大势下&#xff0c;大型政企是向新技术要“新质生产力”的时代先锋。云服务&#xff0c;则是…...

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

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

每日OJ题_哈希表④_力扣219. 存在重复元素 II

目录 力扣219. 存在重复元素 II 解析代码 力扣219. 存在重复元素 II 219. 存在重复元素 II 难度 简单 给你一个整数数组 nums 和一个整数 k &#xff0c;判断数组中是否存在两个 不同的索引 i 和 j &#xff0c;满足 nums[i] nums[j] 且 abs(i - j) < k 。如果存在&am…...

42.坑王驾到第八期:uniCloud报错

uniCloud 报错 今天调用云函数来调试小程序的时候突然暴了一个奇葩错误&#xff0c;require(…).main is not a function。翻官方文档后发现&#xff0c;原来是这样&#xff1a;**如果你写的是云对象&#xff0c;入口文件应为 index.obj.js&#xff0c;如果你写的是云函数入口…...

Linux常用操作命令

Linux常用操作命令 1.文件管理catfile 2.文档编辑3.文件传输4.磁盘管理5.磁盘维护6.网络通讯7.系统管理8.系统设置9.备份压缩10.设备管理 Linux 英文解释为 Linux is not Unix。 Linux内核最初只是由芬兰人李纳斯托瓦兹&#xff08;Linus Torvalds&#xff09;在赫尔辛基大学上…...

OpenCV的常用数据类型

OpenCV涉及的常用数据类型除包含C的基本数据类型,如&#xff1a;char、uchar&#xff0c;int、unsigned int,short 、long、float、double等数据类型外, 还包含Vec&#xff0c;Point、Scalar、Size、Rect、RotatedRect、Mat等类。C中的基本数据类型不需再做说明下面重点介绍一下…...

STM32串口通信—串口的接收和发送详解

目录 前言&#xff1a; STM32串口通信基础知识&#xff1a; 1&#xff0c;STM32里的串口通信 2&#xff0c;串口的发送和接收 串口发送&#xff1a; 串口接收&#xff1a; 串口在STM32中的配置&#xff1a; 1. RCC开启USART、串口TX/RX所对应的GPIO口 2. 初始化GPIO口 …...

《汇编语言》第3版 (王爽) 第14章

第14章 端口 检测点14.1 &#xff08;1&#xff09;.编程&#xff0c;读取CMOS RAM的2号单元的内容。 mov al,2 ;向al写入2 out 70,al ;将2送入端口70h in al,71 ;从端口71h读取2号单元的内容在CMOS RAM中用6个字节存放当前时间&#xff08;以BCD码形式存放&#xff09;&…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

go 里面的指针

指针 在 Go 中&#xff0c;指针&#xff08;pointer&#xff09;是一个变量的内存地址&#xff0c;就像 C 语言那样&#xff1a; a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10&#xff0c;通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...

STM32标准库-ADC数模转换器

文章目录 一、ADC1.1简介1. 2逐次逼近型ADC1.3ADC框图1.4ADC基本结构1.4.1 信号 “上车点”&#xff1a;输入模块&#xff08;GPIO、温度、V_REFINT&#xff09;1.4.2 信号 “调度站”&#xff1a;多路开关1.4.3 信号 “加工厂”&#xff1a;ADC 转换器&#xff08;规则组 注入…...

react更新页面数据,操作页面,双向数据绑定

// 路由不是组件的直接跳转use client&#xff0c;useEffect&#xff0c;useRouter&#xff0c;需3个结合&#xff0c; use client表示客户端 use client; import { Button,Card, Space,Tag,Table,message,Input } from antd; import { useEffect,useState } from react; impor…...