当前位置: 首页 > 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;&…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...