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

LeetCode Hot100 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

思路

        双向链表维护头尾节点,用哈希表键值对寻找节点

代码

class lrulist
{public:int val;int key;lrulist* next;lrulist* last;lrulist(int value, int k) : val(value), key(k), next(nullptr), last(nullptr){}
};
class LRUCache {
public:unordered_map<int, lrulist*> hashmap;lrulist* back;lrulist* front;int size;int cap;void push_front(int value, int key){lrulist* newnode = new lrulist(value, key);hashmap[key] = newnode;if(front){newnode->next = front;front->last = newnode;}elseback = newnode;front = newnode;++size;}void move(lrulist* node){if(node == front)return;if(back == node){back = back->last;if(back)back->next = nullptr;  }else{node->last->next = node->next;node->next->last = node->last; }node->next = front;if(front)front->last = node;front = node;}void del_node(lrulist* node){if(front == node){front = front->next;if(front)front->last = nullptr;}else if(back == node){back = back->last;if(back)back->next = nullptr;}hashmap.erase(node->key);--size;delete node;  }LRUCache(int capacity) : size(0), cap(capacity), front(nullptr), back(nullptr){}int get(int key) {if(hashmap.find(key) != hashmap.end()){move(hashmap[key]);return hashmap[key]->val;}elsereturn -1;}void put(int key, int value) {if(hashmap.find(key) == hashmap.end()){if(size == cap)del_node(back);push_front(value, key);}else{hashmap[key]->val = value;move(hashmap[key]);}}
};

相关文章:

LeetCode Hot100 LRU缓存

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

GESP C++ 2024年06月一级真题卷

一、单选题&#xff08;每题 2 分&#xff0c;共 30 分&#xff09; 第 1 题 在 C 中&#xff0c;下列不可做变量的是 ( ) 。 A. five-Star B. five_star C. fiveStar D. _fiveStar 答案&#xff1a;A 解析&#xff1a;标识符命名规则&#xff0c;标识符由字母、数…...

在 Ubuntu Server 上配置静态 IP 地址

在 Ubuntu Server 上配置静态 IP 地址 测试时使用的Ubuntu server版本是22.04 一、Ubuntu 17.10之前版本 使用 ifupdown 配置文件来设置静态 IP。配置文件通常位于 /etc/network/interfaces。 1.1 编辑 /etc/network/interfaces 文件&#xff1a; sudo vim /etc/network/in…...

数据结构——栈的讲解(超详细)

前言&#xff1a; 小编已经在前面讲完了链表和顺序表的内容&#xff0c;下面我们继续乘胜追击&#xff0c;开始另一个数据结构&#xff1a;栈的详解&#xff0c;下面跟上小编的脚步&#xff0c;开启今天的学习之路&#xff01; 目录 1.栈的概念和结构 1.1.栈的概念 1.2.栈的结构…...

三防平板助力MES系统,实现工厂移动式生产报工

在当今竞争激烈的制造业环境中&#xff0c;提高生产效率、优化生产流程以及实现精准的生产管理已经成为企业生存和发展的关键。 MES系统作为连接企业计划层和控制层的桥梁&#xff0c;在实现生产过程的信息化、数字化和智能化方面发挥着重要作用。与此同时&#xff0c;三防平板…...

WEB渗透Bypass篇-常规函数绕过

常规函数绕过 <?php echo exec(whoami);?> ------------------------------------------------------ <?php echo shell_exec(whoami);?> ------------------------------------------------------ <?php system(whoami);?> ------------------------…...

C++从入门到起飞之——string类的模拟实现 全方位剖析!

&#x1f308;个人主页&#xff1a;秋风起&#xff0c;再归来~&#x1f525;系列专栏&#xff1a;C从入门到起飞 &#x1f516;克心守己&#xff0c;律己则安 目录 1、多文件之间的关系 2、模拟实现常用的构造函数 2.1 无参构造函数 2.2 有参的构造函数 2.3 析构函…...

数据库国产化大趋势下,还需要学习Oracle吗?

由于众所周知的原因&#xff0c;近两年各行各业都开始了数据库国产化替代的进程&#xff0c;从国外商业数据库替换到国产或者开源数据库&#xff0c;相信很多的数据库从业人员会把部分精力转移到其他数据库产品的学习中&#xff0c;也有一些人在大肆的宣扬Oracle已经过时了&…...

WebLogic

二、WebLogic 2.1 后台弱口令GetShell 漏洞描述 通过弱口令进入后台界面&#xff0c;上传部署war包&#xff0c;getshell 影响范围 全版本(前提后台存在弱口令) 漏洞复现 默认账号密码:weblogic/Oracle123weblogic常用弱口令: Default Passwords | CIRT.net这里注意&am…...

Aspose.Words.dll 插入模板表格,使用的是邮件合并MailMerge功能,数据源是DataTable或list对象,实例

本实例中的实例功能有: 1、 Aspose.Words.dll 插入模板指定域替换为文字或html标签,见1 2、Aspose.Words.dll 插入模板表格,使用的是邮件合并MailMerge功能,数据源是DataTable或List对象(将list转换成DataTable),见1和2 3、word转换Pdf文件,见1 4、将多个word输出文…...

同时打开多个微信

注&#xff1a; 以下方法用到的 D:\微信\WeChat\WeChat.exe是我的电脑微信路径&#xff0c;可右击桌面微信快捷方式 > 属性 > 目标查看 以下方法都需要先关掉已登录的微信后操作 <一> 找到微信路径 新建一个txt文件输入以下内容 start D:\微信\WeChat\WeChat.exe …...

MPU6050的STM32数据读取

目录 1. 概述2. STM32G030对MPU6050的读取3. STM32F1xx对MPU6050的读取 1. 概述 项目中&#xff0c;往往需要根据不同的环境使用不同的芯片处理某些数据&#xff0c;当使用不同的芯片对六轴陀螺仪芯片MPU6050进行数据处理中&#xff0c;硬件的连接、I/O口的设置往往需要根据相…...

【微信小程序开发】——奶茶点餐小程序的制作(二)

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;开发者-曼亿点 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 曼亿点 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a…...

Java 文件上传七牛云

Java系列文章目录 文章目录 Java系列文章目录一、前言二、学习内容&#xff1a;三、问题描述四、解决方案&#xff1a;4.1 新建空间4.2 查找密钥4.3 进入开发者中心查找JavaSDK文档4.4 查找文件上传方法4.5 运行测试 五、总结&#xff1a;5.1 学习总结&#xff1a; 一、前言 学…...

大语言模型生成无人系统(如机械臂、无人机等)可以执行的指令序列

大语言模型生成无人系统&#xff08;如机械臂、无人机等&#xff09;可以执行的指令序列涉及将自然语言指令转化为具体的、可执行的指令集合。以下是一个详细的流程&#xff0c;展示了如何从自然语言指令生成无人系统的执行指令序列。 1. 输入自然语言指令 用户输入自然语言指…...

尚硅谷谷粒商城项目笔记——十、调试前端项目renren-fast-vue【电脑CPU:AMD】

十、调试前端项目renren-fast-vue 如果遇到其他问题发在评论区&#xff0c;我看到后解决 1 先下载安装git git官网下载地址 2 登录gitee搜索人人开源找到renren-fast-vue复制下载链接。【网课视频中也有详细步骤】 3 下载完成后桌面会出现renren-fast-vue的文件夹 4 开始调…...

Python 的元组和列表的区别是什么?

以下是 Python 中元组&#xff08;tuple&#xff09;和列表&#xff08;list&#xff09;的主要区别&#xff1a; 1. 语法表示&#xff1a;元组使用小括号 () 来定义&#xff0c;例如 (1, 2, 3) &#xff1b;列表使用方括号 [] 来定义&#xff0c;例如 [1, 2, 3] 。 2. 可变性…...

【Impala】学习笔记

Impala学习笔记 【一】Impala介绍【1】简介&#xff08;1&#xff09;简介&#xff08;2&#xff09;优点&#xff08;3&#xff09;缺点 【2】架构&#xff08;1&#xff09;Impalad&#xff08;守护进程&#xff09;&#xff08;2&#xff09;Statestore&#xff08;存储状态…...

视频汇聚平台EasyCVR接入移动执法记录仪,视频无法播放且报错500是什么原因?

GB28181国标视频汇聚平台EasyCVR视频管理系统以其强大的拓展性、灵活的部署方式、高性能的视频能力和智能化的分析能力&#xff0c;为各行各业的视频监控需求提供了优秀的解决方案。视频智能分析平台EasyCVR支持多协议接入&#xff0c;兼容多类型的设备&#xff0c;包括IPC、NV…...

【Linux基础】Linux基本指令(二)

目录 &#x1f680;前言一&#xff0c;mv指令二&#xff0c;more & less指令2.1 more 指令2.1 less指令 三&#xff0c;重定向技术(重要)3.1 echo指令3.2 输出重定向 >3.3 追加重定向 >>3.4 输入重定向 < 四&#xff0c;head & tail指令4.1 head 指令4.2 t…...

OpenClaw多语言支持:Qwen2.5-VL-7B跨语种图文处理技巧

OpenClaw多语言支持&#xff1a;Qwen2.5-VL-7B跨语种图文处理技巧 1. 为什么需要多语言图文处理 上周我收到一份混合了英文技术文档和中文注释的项目资料&#xff0c;需要整理成统一格式的双语对照版本。手动复制粘贴到翻译工具再调整排版&#xff0c;花了我整整三个小时。这…...

FastAPI + TinyDB并发陷阱与实战:告别数据错乱的解决方案

核心摘要本文针对在FastAPI框架下使用TinyDB&#xff08;JSON文件数据库&#xff09;时遇到的并发写入数据冲突、错乱问题&#xff0c;深入浅出地解释了问题根源&#xff0c;并提供了从“文件锁”到“内存队列”再到“乐观锁”的三种由浅入深的实战解决方案&#xff0c;帮助你根…...

AG-UI协议实战:构建智能体驱动的动态前端交互系统

1. AG-UI协议&#xff1a;智能体与前端交互的新范式 第一次听说AG-UI协议时&#xff0c;我正在为一个电商项目头疼——后台AI生成的商品推荐总需要手动同步到前端&#xff0c;代码里到处是setState和事件监听。直到发现这个协议&#xff0c;才明白原来智能体和前端可以像两个老…...

突破平台壁垒:探索5种在Windows运行Android应用的实战方案与终极选择

突破平台壁垒&#xff1a;探索5种在Windows运行Android应用的实战方案与终极选择 【免费下载链接】APK-Installer An Android Application Installer for Windows 项目地址: https://gitcode.com/GitHub_Trending/ap/APK-Installer 在数字化办公与娱乐深度融合的今天&am…...

电路原理与人生哲学的奇妙对应关系

1. 电路与人生的奇妙映射作为一名在电子行业摸爬滚打十多年的工程师&#xff0c;我常常惊叹于电路原理与人生百态之间的惊人相似。记得刚入行时&#xff0c;我的导师就说过&#xff1a;"读懂电路&#xff0c;就读懂了人生。"当时只觉得是句玩笑话&#xff0c;直到这些…...

OpenClaw批量任务队列:百川2-13B-4bits量化版处理百条邮件自动回复

OpenClaw批量任务队列&#xff1a;百川2-13B-4bits量化版处理百条邮件自动回复 1. 为什么需要邮件自动回复系统 上周我收到了一封来自老客户的紧急咨询邮件&#xff0c;当时正在外地参加会议无法及时回复。等三天后回到电脑前&#xff0c;发现邮箱里堆积了127封未读邮件——其…...

【限时解禁】Cuvil编译器v0.9.3内部架构设计图(含Python动态类型静态化映射表),仅开放72小时

第一章&#xff1a;Cuvil 编译器在 Python AI 推理中的应用Cuvil 是一款面向 AI 工作负载的轻量级领域专用编译器&#xff0c;专为优化 Python 生态中基于 PyTorch 和 ONNX 的模型推理而设计。它通过静态图重写、算子融合与硬件感知调度&#xff0c;在不修改用户代码的前提下&a…...

Windows驱动存储深度管理:从问题诊断到系统优化的完整解决方案

Windows驱动存储深度管理&#xff1a;从问题诊断到系统优化的完整解决方案 【免费下载链接】DriverStoreExplorer Driver Store Explorer [RAPR] 项目地址: https://gitcode.com/gh_mirrors/dr/DriverStoreExplorer 问题发现&#xff1a;驱动管理中的隐形痛点与风险 系…...

实现网页完整捕获:Full Page Screen Capture技术解析与应用指南

实现网页完整捕获&#xff1a;Full Page Screen Capture技术解析与应用指南 【免费下载链接】full-page-screen-capture-chrome-extension One-click full page screen captures in Google Chrome 项目地址: https://gitcode.com/gh_mirrors/fu/full-page-screen-capture-chr…...

企业员工福利平台选型:技术架构与对接难点拆解

企业员工福利平台选型&#xff1a;技术架构与对接难点拆解“选对企业员工福利平台&#xff0c;技术架构与系统对接是决定落地成败的关键——忽略技术适配性的选型&#xff0c;往往会让福利项目陷入‘上线易、用着难’的困境。”随着企业数字化转型加速&#xff0c;员工福利从“…...