​LeetCode解法汇总146. LRU 缓存

news/2024/2/28 1:57:19

 目录链接:

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目:

https://github.com/September26/java-algorithms

原题链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台


描述:

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

提示:

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 105
  • 最多调用 2 * 105 次 get 和 put

解题思路:

* 解题思路:

* 这题最难的其实就是处理双向链表的关系。

* 构建两个方法updateHead和updateTail,分别代表节点变动后处理头部节点和尾部节点。

* 处理头部节点时,分为两种情况,当前节点如果已经是头部节点,则不需要处理。否则,把current的前后节点相连接,然后把current放到头节点。

* 处理尾部节点时,分为3种情况,如果map中只有一个,则当前节点就是尾节点;如果map长度为2,则之前的header就是尾节点;如果current是尾节点,则断开其与前面节点的关系,设置其前面的节点为尾节点。

代码:

class LRUCache
{
public:class Node{public:int key;int val;Node *next;Node *pre;Node(int mkey = 0, int mvalue = 0) : key(mkey), val(mvalue), next(nullptr), pre(nullptr){};};int maxSize = 0;unordered_map<int, Node *> valueMap;Node *header = nullptr;Node *tail = nullptr;LRUCache(int capacity){maxSize = capacity;}int get(int key){if (valueMap.find(key) == valueMap.end()){return -1;}Node *current = valueMap[key];updateTail(current);updateHead(current);return valueMap[key]->val;}void put(int key, int value){if (valueMap.find(key) != valueMap.end()){Node *current = valueMap[key];current->val = value;updateTail(current);updateHead(current);return;}if (valueMap.size() == maxSize){removeNode();}addNode(key, value);}void addNode(int key, int value){Node *current = new Node(key, value);valueMap[key] = current;updateTail(current);updateHead(current);}/*** 把current设置为header*/void updateHead(Node *current){if (header == current){return;}// 链表中删除当前节点if (current->pre != nullptr){current->pre->next = current->next;}if (current->next != nullptr){current->next->pre = current->pre;}// 加入头节点current->next = header;current->pre = nullptr;if (header != nullptr){header->pre = current;}header = current;}void updateTail(Node *current){// 如果长度为1时if (valueMap.size() == 1){tail = current;return;}if (valueMap.size() == 2){tail->pre = current;tail = header;}else if (current == tail){if (tail->pre != nullptr){tail->pre->next = nullptr;}if (valueMap.size() > 1){tail = current->pre;}}}void removeNode(){valueMap.erase(tail->key);Node *tailPre = tail->pre;if (tailPre == nullptr){return;}tailPre->next = nullptr;tail->pre = nullptr;tail = tailPre;}
};


http://www.ppmy.cn/news/1130293.html

相关文章

如何将matlab中的mat矩阵文件在python中读取出来

先安装hdf5storage这个包 pip3 install hdf5storage 然后在当前目录下放入要读取的mat文件 # 将matlab中的mat文件读取出来 import hdf5storagedata hdf5storage.loadmat(inputWeights.mat) print(data[inputWeights])

APP渗透测试

APP反抓包突破 抓包失败分析 工具证书未配置 app不使用HTTP/S协议 反模拟器 1.使用真机进行抓包 2.用模拟器模拟真机 3.逆向删除反模拟器代码打包重新测试 反证书 SSL证书绑定分为单向校验和双向校验&#xff0c;单向校验就是客户端校验服务端的证书&#xff0c;双向…

QT使用前的知识

QT使用前的知识 常用的快捷键 源文件的内容解释 .pro文件的解释 头文件的解释 构建新的对象—组成对象树 槽函数 自定的信号和槽 槽函数的信号是一个重载函数时 电机按钮触发信号 调用无参数的信号 断开信号

【Linux】 du 命令使用

问题 No space left on device 请求接口返回 java.io.IOException: No space left on device 设备上没有剩余空间 怎么解决问题&#xff1a; 查看这篇文章&#xff1a;一次 linux 服务器磁盘使用情况排查 我们提到命令&#xff1a;du -sh * 到底这个命令是干什么的咱们…

AI类APP能做什么

AI类APP可以实现多种功能&#xff0c;涵盖了各种领域和用途。以下是一些常见的AI类APP示例以及它们主要实现的功能&#xff0c;希望对大家有所帮助。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#xff0c;欢迎交流合作。 1.语音助手&#xff08;Voice Assis…

【Python基础】S01E12 json 文件简单处理

S01E12 文件&#xff08;下&#xff09; json 数据基本处理读取 json 数据写入 json 数据 一个应用场景 本文将主要围绕 json 格式字符串的读取与存储做介绍。关于普通 txt 文件的读写&#xff0c;请见&#xff1a;【S01E11 文件&#xff08;上&#xff09;】&#xff1a;https…

springboot(41) : 转发所有请求及鉴权

maven依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web</artifactId></dependency><dependency><groupId>com.alibaba</groupId><artifactId>fastjson</art…

CSS详细基础(六)边框样式

本期是CSS基础的最后一篇~ 目录 一.border属性 二.边框属性复合写法 三.CSS修改表格标签 四.内边距属性 五.外边距属性 六.其他杂例 1.盒子元素水平居中 2.清除网页内外元素边距 3.外边距的合并与塌陷 4.padding不会撑大盒子的情况 七.综合案例——新浪导航栏仿真 …

八叉树C++简单实现

八叉树&#xff08;Octree&#xff09;是一种空间分割数据结构&#xff0c;用于在三维空间中对对象进行高效的存储和查询。 将三维空间划分为八个相等大小的子立方体&#xff08;八个子节点&#xff09;&#xff0c;每个子节点可以进一步细分为八个子节点&#xff0c;以此类推。…

【Oracle】Oracle系列之十一--PL/SQL

文章目录 往期回顾前言1. PL/SQL语句块组成2. 变量的声明与使用&#xff08;1&#xff09;变量声明&#xff08;2&#xff09;变量赋值 3. 控制语句&#xff08;1&#xff09;分支语句&#xff08;2&#xff09;循环语句 4. 异常处理&#xff08;1&#xff09;系统异常&#xf…

ABB LDGRB-01 3BSE013177R1 数字量输入模块

ABB LDGRB-01 3BSE013177R1 是一种数字量输入模块&#xff0c;通常用于工业自动化和控制系统中&#xff0c;用于监测和采集数字信号输入。以下是这种类型数字量输入模块的一般功能和特点&#xff1a; 数字信号采集&#xff1a;ABB LDGRB-01 3BSE013177R1 模块的主要功能是采集数…

echarts 折线组件

echarts 折线组件 <template><div class"lineChartsTemplate" :id"chartsId"></div> </template><script> export default {name: "lineChartsTemplate",components: {},props: {xData: {type: Array,default: ()…

章节2:Webshell介绍

章节2&#xff1a;Webshell介绍 一句话木马 代码短&#xff0c;只有一行代码。 场景多&#xff0c;可以单独生成文件&#xff0c;也可以插入到图片中。 安全性高&#xff0c;隐匿性强&#xff0c;可变形免杀 小马 体积小&#xff0c;功能少 只有文件上传功能 大马 体积…

Elasticsearch keyword 中的 ignore_above配置项

1. ignore_above 关于es mapping的keyword ignore_above配置项的解释如下&#xff1a; Do not index any string longer than this value. Defaults to 2147483647 so that all values would be accepted. 不会索引大于ignore_above配置值的数据&#xff0c;默认值2147483647字…

原型模式 创建型模式之二

一、原型&#xff08;Prototype&#xff09;模式概述 DP书上的定义为&#xff1a;用原型实例指定创建对象的种类&#xff0c;并且通过拷贝这些原型创建新的对象。其中有一个词很重要&#xff0c;那就是拷贝(既clone)。可以说&#xff0c;拷贝(clone)是原型模式的精髓所在。其中…

《Upload-Labs》01. Pass 1~13

Upload-Labs 索引前言Pass-01题解 Pass-02题解总结 Pass-03题解总结 Pass-04题解 Pass-05题解总结 Pass-06题解总结 Pass-07题解总结 Pass-08题解总结 Pass-09题解 Pass-10题解 Pass-11题解 Pass-12题解总结 Pass-13题解 靶场部署在 VMware - Win7。 靶场地址&#xff1a;https…

【CTFHUB】SSRF绕过方法之靶场实践(二)

SSRF POST请求 提示信息&#xff1a; 这次是发一个HTTP POST请求.对了.ssrf是用php的curl实现的.并且会跟踪302跳转.加油吧骚年 首先测试了http的服务请求&#xff0c;出现对话框 输入数值后提示&#xff1a;只能接受来自127.0.0.1的请求 右键查看源码发现key值 通过file协…

MySQL学习笔记24

MySQL的物理备份&#xff1a; xtrabackup备份介绍&#xff1a; xtrabackup优缺点&#xff1a; 优点&#xff1a; 1、备份过程快速、可靠&#xff08;因为是物理备份&#xff09;&#xff1b;直接拷贝物理文件。 2、支持增量备份&#xff0c;更为灵活&#xff1b; 3、备份…

MySQL数据库基本操作--DDL

文章目录 1. DDL2. 对数据库的常用操作3. 对表结构的常用操作数据类型数值类型字符串类型日期类型 基本操作修改表结构格式 1. DDL DDL(Data Definition Language)&#xff0c;数据定义语言&#xff0c;该语言部分包括以下内容&#xff1a; 对数据库的常用操作对表结构的常用…

android 11后文件读写访问权限申请

android 11后对文件读写访问权限管理 与 android 10又有了新的要求&#xff0c;导致在读写或者访问时出现error:java.io.FileNotFoundException: /storage/emulated/0/file_path open failed: EACCES (Permission denied)&#xff0c;以下为android 11文件管理权限申请办法 im…
最新文章