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

LeetCode Medium|【146. LRU 缓存】

力扣题目链接

题意:本题的题意就是希望我们设计一个满足 LRU 缓存的数据结构,LRU即最近最少使用。
需要我们实现 get 和 put 方法,即从缓存中获取值和设置缓存中值的方法。
还有一个约束条件就是缓存应当有容量限制,如果实现 put 方法的时候,没有空闲的空间的话,需要淘汰一个最久没有使用的 key
同时要求 get 和 put 的时间复杂度是 O(1)

其实关于 LRU 最类似的一种应用就是浏览器记录,随着我们打开的浏览器越来越多,浏览历史表就会越来越长,如果我们想要打开某个浏览页面,也会直接从缓存中读取,并且由于我们打开了历史记录中的某个浏览页面,它会成为最新的那条记录。

文章目录

  • 测试用例解读
  • 总体代码
  • 简洁实现
    • 类成员变量
    • 构造函数
    • get 方法
    • put 方法

测试用例解读

可以直接看 B 站视频 :【大厂面试官让我手写LRU缓存,还好提前抱了佛脚,春招有希望了】(具体位置从 3:00开始)

首先我们一个一个解决上面提出的几个问题:

  • 首先关于我们要求的 get 查询方法,很直观的一个想法就是使用 map 来进行实现,不过他只能实现查询时间复杂度为 O(1),但是由于 map 本身是无序的,所以我们希望他能够有新旧顺序的信息。
  • 很直观的思路,我们每次新建一个键值对的时候,就把这个 key-value 放入一个链表的头,我们每次存入新的节点,我们就把其作为新的头。这样我们链表的头部永远都是那个最新的 key-value;链表的尾部就是最久未使用的键值对
  • 但是我们仍然有一个很重要的问题无法实现:如果我们查询了某个 key-value ,并且该节点在链表的中间位置,那么我们就不能及时得将该节点放到链表的头部。因为我们的 map 是以 key-value 来进行存取的,所以我们不能在链表中及时找到对应的节点
  • 为了应对上面的情况,有一个比较好的思路就是,当我们存储节点时,map 中的 key 就是该节点的键,map 中的 value 就是该节点所在链表的节点(ListNode*)。通过这样的方法,我们可以快速定位到链表节点,而不需要根据别的信息进行遍历。
  • 根据以上的要求,我们可以知道,使用单向链表是无法实现上述想法的,因为我们的节点是需要往前移动到链表头部,所以这里的数据结构使用双向链表。

总上所述,我们的代码雏形就出来了。

总体代码

  • 首先定义双向链表的节点结构:每个结构包括 key-value 的值和 prev 和 next 指针,并且定义两个构造函数
struct Node {int key, value;Node *prev, *next;Node() : key(0), value(0), prev(nullptr), next(nullptr) {}Node(int key, int value) : key(key), value(value), prev(nullptr), next(nullptr) {}
};
  • 下面来实现 LRU 缓存:定义链表的虚拟头、尾节点;哈希表来存储 key 和 双向链表节点 的映射关系;最后是我们的容量大小,以及当前已使用的大小。
class LRUCache {
private:std::unordered_map<int, Node*> hashMap_;int capacity_, size_;Node *dummyHead_, *dummyTail_;
};
  • 实现 LRUCache 的构造函数:
class LRUCache {
private:...
public: LRUCache(int capacity) : capacity_(capacity), size_(0) {dummyHead_ = new Node();dummyTail_ = new Node();dummyHead_->next = dummyTail_;dummyTail_->prev = dummyHead_;}
  • 接下来我们来实现从链表中删除节点和插入节点到链表头的方法,该方法是其中的 get 和 put 方法中的重要:
    void removeNode(Node* node) {node->prev->next = node->next;node->next->prev = node->prev;}// 在头节点处插入一个 nodevoid addNodeToHead(Node* node) {node->prev = dummyHead_;node->next = dummyHead_->next;dummyHead_->next->prev = node;dummyHead_->next = node;}
  • 接下来实现重要的 get 方法:首先我们需要确定节点时候在哈希表中:
    int get(int key) {if (hashMap_.find(key) != hashMap_.end()) {Node* node = hashMap_[key];removeNode(node);addNodeToHead(node);return node->value;}return -1;}
  • 随后是设置节点的值:如果该节点在哈希表中存在的话,我们就重新设置其节点的值,随后更新其位置在最前面;如果不存在的话,说明要插入一个新的节点,我们首先要判断一下容量,如果容量达到了上限,我们就需要从链表的尾部淘汰一个节点,然后在进行插入
    void put(int key, int value) {if (hashMap_.find(key) != hashMap_.end()) {Node* node = hashMap_[key];node->value = value;removeNode(node);addNodeToHead(node);} else {if (size_ == capacity_) {Node* removed = dummyTail_->prev;hashMap_.erase(removed->key);removeNode(removed);delete removed;size_--;}Node* node = new Node(key, value);addNodeToHead(node);hashMap_[key] = node;size_++;}}

简洁实现

这里介绍一个简介实现,如下:

class LRUCache {
public:LRUCache(int capacity) : capacity_(capacity) {}int get(int key) {auto it = cacheMap.find(key);if (it == cacheMap.end()) {return -1; // Key not found} else {// Move the accessed (key, value) pair to the front of the cacheListcacheList.splice(cacheList.begin(), cacheList, it->second);return it->second->second;}}void put(int key, int value) {auto it = cacheMap.find(key);if (it != cacheMap.end()) {// Key already exists, update the value and move it to the frontit->second->second = value;cacheList.splice(cacheList.begin(), cacheList, it->second);} else {if (cacheList.size() == capacity_) {// Cache is full, remove the least recently used itemauto last = cacheList.back();cacheMap.erase(last.first);cacheList.pop_back();}// Insert the new key-value pair at the frontcacheList.emplace_front(key, value);cacheMap[key] = cacheList.begin();}}private:int capacity_;std::list<std::pair<int, int>> cacheList; // Stores the (key, value) pairsstd::unordered_map<int, std::list<std::pair<int, int>>::iterator> cacheMap; // Maps key to the corresponding iterator in cacheList
};

类成员变量

首先定义一个类成员变量:

class LRUCache {
private:int capacity_;std::list<std::pair<int, int>> cacheList_; // Stores the (key, value) pairsstd::unordered_map<int, std::list<std::pair<int, int>>::iterator> cacheMap_; // Maps key to the corresponding iterator in cacheList
};

这里的 cacheList 即我们之前所维护的那个双向链表;
cacheMap 就是我们之前维护的那个 hashMap ,key 是键值, value 是我们之前的链表节点。

在此之前,我们自己定义个用于缓存的节点,但是我们可以直接使用 std::pair<int, int> 来代替我们自己构造的类;

除此之外:std::pair<int, int>>::iterator 是一个类型声明,用于表示指向 std::list<std::pair<int, int>> 中元素的迭代器,这个迭代器类型可以用来遍历或访问 std::list 容器中的元素。

接下来我们开始进行主要成员方法的实现:

构造函数

class LRUCache {
public:LRUCache(int capacity) : capacity_(capacity) {}
private:...
};

get 方法

    int get(int key) {auto it = cacheMap_.find(key);if (it == cacheMap_.end()) {return -1; // Key not found} else {// Move the accessed (key, value) pair to the front of the cacheListcacheList_.splice(cacheList_.begin(), cacheList_, it->second);return it->second->second;}}

put 方法

    void put(int key, int value) {auto it = cacheMap_.find(key);if (it != cacheMap_.end()) {// Key already exists, update the value and move it to the frontit->second->second = value;cacheList_.splice(cacheList_.begin(), cacheList_, it->second);} else {if (cacheList_.size() == capacity_) {// Cache is full, remove the least recently used itemauto last = cacheList_.back();cacheMap_.erase(last.first);cacheList_.pop_back();}// Insert the new key-value pair at the frontcacheList_.emplace_front(key, value);cacheMap_[key] = cacheList_.begin();}}

相关文章:

LeetCode Medium|【146. LRU 缓存】

力扣题目链接 题意&#xff1a;本题的题意就是希望我们设计一个满足 LRU 缓存的数据结构&#xff0c;LRU即最近最少使用。 需要我们实现 get 和 put 方法&#xff0c;即从缓存中获取值和设置缓存中值的方法。 还有一个约束条件就是缓存应当有容量限制&#xff0c;如果实现 put …...

(南京观海微电子)——LCD OTP(烧录)介绍

OTP OTP只是一种存储数据的器件&#xff0c;全写:ONETIMEPROGRAM。 OTP目的&#xff1a;提高产品的一致性 客户端的接口不支持和我们自己的产品IC之间通信&#xff0c;即不支持写初始化&#xff0c;所以产品的电学功能以及光学特性需要固化在IC中&#xff0c;所以需要我们来进行…...

[E二叉树] lc572. 另一棵树的子树(dfs+前中序判断+树哈希+树上KMP+好题)

文章目录 1. 题目来源2. 题目解析 1. 题目来源 链接&#xff1a;572. 另一棵树的子树 2. 题目解析 看到这个题目就感觉不简单&#xff0c;因为写了写 dfs 版本的&#xff0c;发现好像不太会… 还是简单粗暴一点&#xff0c;直接搞一个 前序中序&#xff0c;进行判断即可。我…...

C# 设计模式之简单工厂模式

总目录 前言 本文是个人基于C#学习设计模式总结的学习笔记&#xff0c;希望对你有用&#xff01; 1 基本介绍 简单工厂模式 定义&#xff1a;用于创建对象&#xff0c;将对象的创建与使用分离。 简单工厂模式中用于创建实例的方法是静态(static)方法&#xff0c;因而简单工厂…...

mac中dyld[5999]: Library not loaded: libssl.3.dylib解决方法

需要重新安装下openssl3.0版本 brew reinstall openssl3.0 安装后执行还是报错&#xff0c;需要找到openssl的安装路径 /opt/homebrew/Cellar/openssl3.0/3.0.14/lib/ 将libssl.3.dylib和libcrypto.3.dylib拷贝到自己的二进制文件同目录下&#xff0c;再执行二进制文件就可…...

python 容器

文章目录 数据容器特点比较通用序列操作示例代码1. s.index(x[, i[, j]])2. s.count(x)示例代码注意事项代码解释输出结果 数据容器的通用转换1. list()2. tuple()3. str()4. set()5. dict()6. enumerate()7. zip()8. sorted()9. reversed()10. map()11. filter()12. join()示例…...

微信小程序中Component中如何监听属性变化

1.在父组件的.json文件中引入子组件&#xff1a; "usingComponents": {"articleList":"../../components/articleList/articleList",}2.在父组件中给子组件绑定数据 <articleList num"{{number}}"></articleList>3.子组…...

【Python 逆向滑块】(实战五)逆向滑块,并实现用Python+Node.js 生成滑块、识别滑块、验证滑块、发送短信

逆向日期&#xff1a;2024.08.03 使用工具&#xff1a;Python&#xff0c;Node.js 本章知识&#xff1a;滑块距离识别&#xff0c;滑块轨迹生成&#xff0c;验证滑块并获取【validate】参数 文章难度&#xff1a;中等&#xff08;没耐心的请离开&#xff09; 文章全程已做去敏处…...

微服务架构设计的最佳实践

在当今快速变化的软件开发环境中&#xff0c;微服务架构因其灵活性、可扩展性和可维护性而逐渐成为大型分布式系统的首选架构模式。然而&#xff0c;成功实施微服务架构并非易事&#xff0c;它要求开发团队遵循一系列最佳实践来确保系统的可靠性、效率和可管理性。本文将探讨微…...

样式与特效(3)——实现一个测算页面

这次我们使用前端实现一个简单的游戏页面,理论上可以增加很多玩法&#xff0c;&#xff0c;但是这里为了加深前端的样式和JS点击事件&#xff0c;用该案例做练习。 首先需要掌握手机端的自适应&#xff0c;我们是只做手机端玩家页面 。需要允许自适应手机端页面&#xff0c; 用…...

芯片制造过程4光刻机

以下内容均取自哔哩哔哩up主谈三圈 链接: 芯片制造详解04&#xff1a;光刻技术与基本流程&#xff5c;国产之路不容易 1.光刻原理 通过光掩膜、光刻机、光刻胶进行光刻 光掩膜是芯片的蓝图&#xff0c;是一张刻有集成电路板图的玻璃遮光板光刻机就像一台纳米级的打印机&#…...

Nexus3 Repository代理pypi设置与应用

目录 1. 创建Blob库并指定路径 2. 创建pypi阿里镜像源 3. 创建pypi腾讯镜像源 4. 创建一个pypi组管理 5. 配置pip 6. 下载测试 扩展&#xff1a;配置好后无法下载解决思路。 Nexus 存储库中的 Blob 存储是指一种用于存储大量非结构化数据的技术。在 Nexus 存储库的上下文…...

PMP–知识卡片--燃起图

燃起图用两条曲线分别绘制随时间的推移、完成的工作量和总工作量的变化情况。它不仅能清晰地展示项目进度&#xff0c;还是对团队成员的一种激励形式。 使用燃起图可以更好地了解进度、范围变更和预期完成时间&#xff0c;它为所有相关方提供了更清晰的进度状态。 燃起图根据工…...

63 epoll服务器 (ET模式)

基于LT模式修改&#xff0c;并加入前面的应用层计算器&#xff0c;实现稍完整的服务器功能 1.修改tcp_socket.hpp&#xff0c;新增非阻塞读和非阻塞写接口 2.对于accept返回的new_sock加上EPOLLET这样的选项 注意&#xff1a;此代码暂时未考虑listen_sock ET的情况&#xff0c…...

AI Agent

一&#xff0c;什么是AI Agent&#xff1f; AI Agent&#xff08;人工智能代理&#xff09;是一种能够自主执行任务和决策的智能系统。它通常具备感知环境、处理信息和采取行动的能力&#xff0c;能够模拟人类的思维和行为方式。 它可以是软件程序&#xff0c;也可以是嵌入式…...

select

select函数简介: select是Linux中常用的多路复用IO机制&#xff0c;它允许程序同时监控多个文件描述符&#xff08;可以是套接字socket&#xff0c;也可以是普通文件&#xff09;的读、写和异常事件。 #include <sys/select.h> #include <sys/time.h> …...

按照指定格式打印pprint()

【小白从小学Python、C、Java】 【考研初试复试毕业设计】 【Python基础AI数据分析】 按照指定格式打印 pprint() [太阳]选择题 根据给定的Python代码&#xff0c;哪个选项是正确的&#xff1f; from pprint import pprint data { name: A, age: 30, hobbies:…...

Study--Oracle-07-ASM常用维护操作(五)

一、ASM创建新的磁盘组 1、查看系统中可用的磁盘 set lines 150; col name for a35; col path for a35; select group_number,path, state, name, total_mb, free_mb from v$asm_disk; 2、磁盘组操作 创建磁盘组 create DISKGROUP DATADGV2 EXTERNAL REDUNDANCY DISK /dev…...

[Git][分支管理][上]详细讲解

目录 1.理解分支2.创建分支3.切换分支4.合并分支5.删除分支 1.理解分支 感性理解&#xff1a;分支可以理解为平行宇宙&#xff0c;但是在用户需要的时候&#xff0c;可以将两个平行宇宙合并&#xff0c;此时两个平行宇宙的效果将会"叠加"理性理解&#xff1a;每次提…...

C语言指针(1)

目录 一、内存和地址 1、生活中的例子 2、内存的关系 二、指针变量和地址 1、&符号&#xff0c;%p占位符 2、一个简单的指针代码。 3、理解指针 4、解引用操作符 5、指针变量的大小。 三、指针变量类型的意义 1、指针解引用的作用 2、指针指针 3、指针-指针 4…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...