【高频面试题】LRU缓存
文章目录
- 1 相关前置知识（OS）
- 2 面试题 16.25. LRU 缓存
- 2.1 题面
- 2.2 示例
- 2.3 解法1 （双端队列+哈希表）
- 思路
- 2.4 解法2
- 思路
- 3 参考
1 相关前置知识（OS）
- 为什么需要页面置换算法：当进程运行时，若其访问的页面不在内存需要将其调入，但内存已无空闲空间时，就需要从内存中调出一页，换出到外存，选择调出哪个页面的算法就称为页面置换算法。页面的换入，换出需要磁盘I/O开销较大，因此要设计一个好的页面置换算法追求更低的缺页率。
- 常见的页面置换算法：OPT(最佳置换算法) FIFO（先进先出置换算法） LRU（最近最久未使用置换算法） CLOCK（时钟置换算法）
- 什么是LRU算法：简单来讲就是将一些元素放在一个容量固定的容器中进行存取，由于容器的容量有限，该容器就要保证那些最近才被用到的元素始终在容器内，而将已经很久没有用的元素剔除，实现容器内元素的动态维护。这种算法是一种缓存维护策略，因为缓存空间有限，让缓存中存储的都是最近才被用到的元素可以实现系统缓存的高效运作。
2 面试题 16.25. LRU 缓存
2.1 题面
设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。
它应该支持以下操作：
- 获取数据
get和 写入数据put。 - 获取数据
get(key)- 如果密钥(key)存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。 - 写入数据
put(key, value)- 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。 - 注意：要求
get和put的时间复杂度为O(1)
2.2 示例
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
2.3 解法1 （双端队列+哈希表）
思路
- 使用双端队列维护，队尾是最近使用的，队头是最久未使用的，哈希表则维护key-value，此外注意在get时若元素存在则要重新将该元素移动到队列尾部，put若元素已存在，则要更新value，并将元素调整到队尾。
class LRUCache {
private:int capacity;std::deque<int> dq; std::unordered_map<int, int> mp;
public:LRUCache(int capacity) : capacity(capacity) {}int get(int key) { // 若元素存在则将该元素移到队尾if (mp.find(key) != mp.end()) {dq.erase(std::remove(dq.begin(), dq.end(), key), dq.end());dq.push_back(key);return mp[key];}return -1;}void put(int key, int value) {if (mp.find(key) != mp.end()) {// 如果 key 已存在，更新 value，并调整到队尾mp[key] = value;dq.erase(std::remove(dq.begin(), dq.end(), key), dq.end());dq.push_back(key);} else {if (dq.size() == capacity) {int lru_key = dq.front();mp.erase(lru_key);dq.pop_front();}mp[key] = value;dq.push_back(key);}}
};
2.4 解法2
解法1的效率十分低，而且没有满足时间复杂度O（1）的条件，效率只击败了5%，我们想想要如何实现O（1），什么数据结构支持O（1）维护两端元素呢，我们可以用双向链表来实现。
思路
-
使用双向链表+哈希表维护，表头维护最近使用的元素，表尾维护最久未使用的元素。这里我们要使用双向链表实现在表头添加一个元素、删除某个节点这两个操作。
-
对于
get操作，首先判断key是否存在：如果key不存在，则返回 -1；如果key存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。 -
对于
put操作，首先判断key是否存在：如果key不存在，使用key和value创建一个新的节点，在双向链表的头部添加该节点，并将key和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；如果key存在，则与get操作类似，先通过哈希表定位，再将对应的节点的值更新为value，并将该节点移到双向链表的头部。
class Node {
public: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) {}
};class LRUCache {
private:std::unordered_map<int, Node*> cache;Node* dummy; // 头节点 表头维护最近使用的 表尾维护最久未使用的int capacity;// 删除一个节点void remove(Node *p) {p->prev->next = p->next;p->next->prev = p->prev;}// 表头添加一个节点void push_front(Node *p) {p->prev = dummy;p->next = dummy->next;p->prev->next = p;p->next->prev = p;}Node* get_node(int key) {auto it = cache.find(key);if (it == cache.end()) return nullptr;auto node = it->second;remove(node); // 将元素移出push_front(node); // 放在表头return node;}
public:LRUCache(int capacity) {this->capacity = capacity;dummy = new Node();dummy->next = dummy;dummy->prev = dummy;}int get(int key) {auto node = get_node(key);return node ? node->value : -1;}void put(int key, int value) {auto node = get_node(key);if (node) { //若存在该元素node->value = value; // 更新valuereturn ;}cache[key] = node = new Node(key, value);push_front(node); // 放在表头if (cache.size() > capacity) { // 超容量auto back = dummy->prev;cache.erase(back->key);remove(back); //去掉尾部元素delete back; // 释放内存}}
};/*** Your LRUCache object will be instantiated and called as such:* LRUCache* obj = new LRUCache(capacity);* int param_1 = obj->get(key);* obj->put(key,value);*/
3 参考
- 【图解】一张图秒懂 LRU！
- 面试题 16.25. LRU 缓存（C++【OPT/FIFO/LRU】操作系统页面置换算法一网打尽）
相关文章：
【高频面试题】LRU缓存
文章目录 1 相关前置知识（OS）2 面试题 16.25. LRU 缓存2.1 题面2.2 示例2.3 解法1 （双端队列哈希表）思路 2.4 解法2思路 3 参考 1 相关前置知识（OS） 为什么需要页面置换算法：当进程运行时&…...
Golang
本文来源 ：腾讯元宝 Go语言（又称Golang）是由Google开发的一种现代编程语言，自2009年发布以来，因其简洁性、高性能和内置并发支持而广受欢迎。以下是关于Go语言的核心特点和优势的总结： 1. 核心特点…...
20250515配置联想笔记本电脑IdeaPad总是使用独立显卡的步骤
20250515配置联想笔记本电脑IdeaPad总是使用独立显卡的步骤 2025/5/15 19:55 百度：intel 集成显卡 NVIDIA 配置成为 总是用独立显卡 百度为您找到以下结果 ?要将Intel集成显卡和NVIDIA独立显卡配置为总是使用独立显卡，可以通过以下步骤实现?ÿ…...
『已解决』Python virtualenv_ error_ unrecognized arguments_--wheel-bundle
📣读完这篇文章里你能收获到 🐍 了解 virtualenv 参数错误的原因及解决方案📦 学习如何正确配置 Python 虚拟环境 文章目录 前言一、问题描述1.1 错误现象1.2 影响范围 二、问题分析2.1 根本原因 三、解决方案3.1 兼容处理3.2 完整解决方案 …...
使用 Apache POI 生成 Word 文档
创建一个包含标题、段落和表格的简单文档。 步骤 1：添加依赖 确保你的项目中已经添加了 Apache POI 的依赖。如果你使用的是 Maven，可以在 pom.xml 中添加以下内容： <dependency><groupId>org.apache.poi</groupId>...
表记录的检索
1.select语句的语法格式 select 字段列表 from 表名 where 条件表达式 group by 分组字段 [having 条件表达式] order by 排序字段 [asc|desc];说明： from 子句用于指定检索的数据源 where子句用于指定记录的过滤条件 group by 子句用于对检索的数据进行分组 ha…...
【PX4飞控】在 Matlab Simulink 中使用 Mavlink 协议与 PX4 飞行器进行交互
这里列举一些从官网收集的比较有趣或者实用的功能。 编写 m 脚本与飞行器建立 UDP 连接，并实时可视化 Mavlink 消息内容，或者读取脚本离线分析数据。不光能显示 GPS 位置或者姿态等信息的时间曲线，可以利用 Matlab Plot 功能快速定制化显示一…...
文章复现|（1）整合scRNA-seq 和空间转录组学揭示了子宫内膜癌中 MDK-NCL 依赖性免疫抑制环境
https://www.frontiersin.org/journals/immunology/articles/10.3389/fimmu.2023.1145300/full 目标：肿瘤微环境(TME)在子宫内膜癌(EC)的进展中起着重要作用。我们旨在评估EC的TME中的细胞群体。 方法：我们从GEO下载了EC的单细胞RNA测序(scRNA-seq)和空…...
自用Vscode 配置c++ debug环境
前言 使用vscode配置c debug环境的好处 1、可以借助vscode方便轻量的扩展和功能 2、避免了传统使用gdb 复杂按键以及不够直观的可视化 3、方便一次运行，断点处查看变量，降低找bug难度 4、某大公司项目采用类似配置，经过实践检验 配置c运行环…...
STM32单片机内存分配详细讲解
单片机的内存无非就两种，内部FLASH和SRAM，最多再加上一个外部的FLASH拓展。在这里我以STM32F103C8T6为例子讲解FLASH和SRAM。 STM32F103C8T6具有64KB的闪存和20KB的SRAM。 一. Flash 1.1 定义 非易失性存储器，即使在断电后，其所…...
从算力困境到创新突破：GPUGEEK如何重塑我的AI开发之旅
目录 从算力困境到创新突破：GPUGEEK如何重塑我的AI开发之旅开发者的算力挣扎：一个不得不面对的现实AI算力市场的尴尬现状：为什么我们需要另辟蹊径1. 资源分配失衡与价格壁垒2. 技术门槛与环境复杂性 GPUGEEK深度剖析：不只是又一个…...
基于OpenCV的人脸微笑检测实现
文章目录 引言一、技术原理二、代码实现2.1 关键代码解析2.1.1 模型加载2.1.2 图像翻转2.1.3 人脸检测 微笑检测 2.2 显示效果 三、参数调优建议四、总结 引言 在计算机视觉领域，人脸检测和表情识别一直是热门的研究方向。今天我将分享一个使用Python和OpenCV实现…...
2025认证杯数学建模第二阶段A题小行星轨迹预测思路+模型+代码
2025认证杯数学建模第二阶段思路模型代码，详细内容见文末名片 一、问题重述 1.1 问题背景 在浩瀚无垠的宇宙中，近地小行星（NEAs）宛如一颗颗神秘的“太空子弹”，其轨道相对接近地球，给我们的蓝色星球带来…...
Uniapp 安卓实现讯飞语音听写（复制即用）
在移动应用开发中，语音交互功能能够极大提升用户体验，让操作更加便捷自然。讯飞语音听写技术凭借其高准确率和稳定性，成为众多开发者的选择。本文将详细介绍如何在 Uniapp 项目中，实现安卓端的讯飞语音听写功能，帮助你…...
【FileZilla】 从事件类型到消息类型的函数形参类型转化
本篇其实是前篇【Filezilla】 dispatch函数重载的例子-CSDN博客的一个补充，其中涉及到【FileZilla】事件调用机制代码解析-CSDN博客中的事件分发机制时钩子函数的参数传递怎么实现的。跟【FileZilla】sftp协议的数据传输上传和下载-CSDN博客同样，用事件是…...
python打卡day26
函数、参数、变量 知识点回顾： 函数的定义变量作用域：局部变量和全局变量函数的参数类型：位置参数、默认参数、不定参数传递参数的手段：关键词参数传递参数的顺序：同时出现三种参数类型时 def function_name(parameter…...
RPC框架源码分析学习（二）
RPC框架源码分析与原理解读 前言 在分布式系统开发中，远程过程调用(RPC)是一项基础且关键的技术。通过对KVstorageBaseRaft-cpp项目RPC模块的源码分析，我深入理解了RPC框架的工作原理和实现细节。本文将从程序员视角分享我的学习心得。 框架概述 本项…...
算法分析：蛮力法
一、实验目的 1 掌握蛮力法的设计思想(利用计算机去穷举所有的可能解,再从中依次找出可行解) 2 掌握蛮力法的具体实现和时间复杂度分析 3 理解蛮力法的常见特性 实验要求：先用伪代码描述利用蛮力法解决的算法解决方案，再用程序实现，计算时间…...
构建RAG混合开发---PythonAI+JavaEE+Vue.js前端的实践
写在前文：之所以设计这一套流程，是因为 Python在前沿的科技前沿的生态要比Java好，而Java在企业级应用层开发比较活跃； 毕竟许多企业的后端服务、应用程序均采用Java开发，涵盖权限管理、后台应用、缓存机制、中间件集成…...
游戏引擎学习第280天:精简化的流式实体sim
回顾并为今天的内容做铺垫 今天的任务是让之前关于实体存储方式的改动真正运行起来。我们现在希望让实体系统变得更加真实和实用，能够支撑我们游戏实际所需的功能。这就要求我们对它进行更合理的实现和调试。 昨天我们基本让代码编译通过了，但实际上还…...
小程序映射逻辑处理
onLoad: function (options) { // 如果直接从options获取数据 this.setData({ jielunpin:发羽音, birthStr: 1944-01-01 }); // 处理诊断结论 this.processJielunpin(); // 添加一个处理诊断结论的函数 processJielunpin: function() { // 获取jielunpin和birthSt…...
亚马逊，temu测评采购低成本养号策略：如何用一台设备安全批量管理买家账号
只要能够巧妙规避平台的检测和风控措施，测评便可安全进行。 自养号测评，它更便于卖家掌控，且能降低风险。现在很多卖家都是自己养号，自己养号都是精养，不是自动的机刷，买家账号掌握在自己手里，更…...
TCP实现安全传输的核心机制 + TCP的报文讲解（全程图文讲解）
目录 一、TCP的协议和数据报格式 二、TCP常见的核心机制 1. 确认应答 2. 超时重传 3. 连接管理 三次握手（建立连接） 四次挥手（断开连接） 常见的状态和整体的传输流程 4. 滑动窗口 5. 流量控制 6. 拥塞控制 7. 延迟应…...
【测试工具】selenium和playwright如何选择去构建自动化平台
构建UI自动化平台服务，在底层选择自动化框架，selenium和playwright这两个如何选择 在构建UI自动化平台服务时，选择底层自动化框架（如 Selenium 和 Playwright）是一个非常关键的决策，直接影响平台的性能、可…...
ES常识8：ES8.X如何实现热词统计
文章目录 一、数据采集与存储设计1. 确定需记录的字段2. 设计搜索日志索引 二、数据写入与采集三、热门搜索词统计（核心逻辑）1. 基础版：近 7 天热门搜索词（按出现次数排序）2. 进阶版：加权热门词（…...
可解释性AI 综述《Explainable AI for Industrial Fault Diagnosis: A Systematic Review》
一、研究背景与动因（Background & Motivation） 随着工业4.0与工业5.0的发展，工业生产越来越依赖自动化与智能化手段，以实现高效、预测性维护与运行优化。在这一背景下，人工智能（AI）与机器学…...
数据可视化-----子图的绘制及坐标轴的共享
目录 绘制固定区域的子图 （一）、绘制单子图 subplot()函数 Jupyter Notebook的绘图模式 （二）、多子图 subplots()--可以在规划好的所有区域中一次绘制多个子图 （三）、跨行跨列 subplot2grid()---将整…...
nginx 配置
proxy_pass 结尾斜杠规则 不带斜杠：保留原始请求路径。 location /api {proxy_pass http://backend; # 转发到 http://backend/api }带斜杠：剥离 location 匹配的路径前缀。 location /api/ {proxy_pass http://backend/; # 转发到 http://back…...
《从零开始入门递归算法：搜索与回溯的核心思想 + 剑指Offer+leetcode高频面试题实战（含可视化图解）》
一.递归 1.汉诺塔 题目链接：面试题 08.06. 汉诺塔问题 - 力扣（LeetCode） 题目解析：将A柱子上的盘子借助B柱子全部移动到C柱子上。 算法原理：递归 当A柱子上的盘子只有1个时，我们可以直接将A上的盘子直…...
船舶制造业数字化转型：驶向智能海洋新航道
在全球海洋经济蓬勃发展的当下，船舶制造业作为海洋产业的重要支柱，正面临着前所未有的机遇与挑战。船舶制造周期长、技术复杂，从设计图纸到最终交付，涉及成千上万的零部件和复杂的工艺流程，传统制造模式已难以满足市场…...
SpringBoot 自动装配流程
Spring Boot 的自动装配（Auto Configuration）是其最核心的特性之一，它让你能“开箱即用”，极大简化了配置。下面是 Spring Boot 自动装配的整体流程（从启动到生效） 的详细解析： ✅ 一、整体流程…...
Vue 3 实现后端 Excel 文件流导出功能（Blob 下载详解）
💡 本文以告警信息导出为例，介绍 Vue 3 中如何通过 Axios 调用后端接口并处理文件流，实现 Excel 自动下载功能。 📑 目录 一、前言 二、后端接口说明 三、前端实现思路 四、导出功能完整代码 五、常见问题处理 六、效果展示 …...
基于IBM BAW的Case Management进行项目管理示例
说明：使用IBM BAW的难点是如何充分利用其现有功能根据实际业务需要进行设计，本文是示例教程，因CASE Manager使用非常简单，这里重点是说明如何基于CASE Manager进行项目管理，重点在方案设计思路上，其中涉及的…...
《Python星球日记》 第78天：CV 基础与图像处理
名人说：路漫漫其修远兮，吾将上下而求索。—— 屈原《离骚》 创作者：Code_流苏(CSDN)（一个喜欢古诗词和编程的Coder😊） 目录 一、计算机视觉（CV）简介1. 什么是计算机视觉？2. 计算机视觉的应用场景3. 图像的基本属性a》像素（Pixel）b》通道（Channel）c》分辨率（Res…...
Google DeepMind 推出AlphaEvolve
每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗？订阅我们的简报，深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同，从行业内部的深度分析和实用指南中受益。不要错过这个机会，成为AI领…...
Flink 1.13.2 日志配置优化：保留最近 7 天日志文件
Flink 1.13.2 日志配置优化：保留最近 7 天日志文件 在使用 Apache Flink 1.13.2 进行流处理任务时，合理的日志配置对于作业的监控、调试和故障排查至关重要。本文将介绍如何通过修改log4j.properties文件，将 Flink 的默认日志配置升级为保留最近 7 天的日志文件配置，并解决…...
【优化算法】协方差矩阵自适应进化策略（Covariance Matrix Adaptation Evolution Strategy，CMA-ES）
CMA-ES（Covariance Matrix Adaptation Evolution Strategy）算法是一种无导数、基于多元正态分布的迭代优化方法，通过自适应地调整搜索分布的均值、协方差矩阵和步长，能够高效地解决非线性、非凸的连续优化问题。 算法以最大似然和…...
基于Leaflet和天地图的免费运动场所WebGIS可视化-以长沙市为例
目录 前言 一、免费运动场所数据整理 1、本地宝数据简介 2、Java后台数据解析 二、Leaflet前端地图展示 1、基础数据准备 2、具体位置及属性标记 三、成果展示 1、空间位置分布 2、东风路立交桥运动公园 3、芙蓉区花侯路浏阳河大桥下方 4、梅岭国际小区 5、湖南大学…...
399. 除法求值
https://leetcode.cn/problems/evaluate-division/description/?envTypestudy-plan-v2&envIdtop-interview-150思路：读完题后我们可以发现这题的考察已经很明确了就是考我们矩阵，我们将矩阵构建出来后，这题就变成可达性分析题了。 所以解…...
QMK固件OLED显示屏配置教程：从零开始实现个性化键盘显示（实操部分）
QMK固件OLED显示屏配置教程：从零开始实现个性化键盘显示 📢 前言： 作为一名键盘爱好者，近期研究了QMK固件的OLED显示屏配置，发现网上的教程要么太过复杂，要么过于简单无法实际操作。因此决定写下这篇教程，从零基础出发，带大家一步步实现键盘OLED屏幕的配置与个性化显示…...
深度解析 Meta 开源 MR 项目《North Star》：从交互到渲染的沉浸式体验设计
🌌 一、项目概览：什么是 North Star？ North Star 是由 Meta 官方推出并开源 的一款面向 Meta Quest 平台 的混合现实（MR）视觉演示项目。它不仅上线了 Horizon Store，更以完整的技术栈与高质量内容向开发者展示了如何在 VR/MR 设备上实现“视觉上限”和“交互潜力”的结…...
使用VS Code通过SSH编译Linux上的C++程序
引言 在软件开发领域，跨平台开发是一项常见需求。特别是对于C开发者来说，有时需要在Windows环境下编写代码，但却需要在Linux环境中编译和运行。这种情况在系统编程、嵌入式开发或高性能计算领域尤为常见。 Visual Studio Code (VS Code) 提…...
Datawhale 5月llm-universe 第2次笔记
第二章 使用 LLM API 开发应用 名词解释 Temperature 参数/场景低 Temperature（0 ~ 0.3）高 Temperature（0.7 ~ 1.0）输出特点保守、稳定、可预测创造性强、多样化、不可预测语言模型行为更少的随机性，倾向于选择高概…...
【Vue】CSS3实现关键帧动画
关键帧动画 两个重点keyframesanimation子属性 实现案例效果展示： 两个重点 keyframes 和 animation 作用：通过定义关键帧（keyframes）和动画(animation)规则，实现复杂的关键帧动画。 keyframes 定义动画的关键帧序列…...
Spring 模拟转账开发实战
一、转账业务场景分析 转账是金融类应用的核心场景之一，涉及付款方扣减金额和收款方增加金额两个关键操作。在开发中需解决以下问题： 业务层与数据层解耦：通过分层架构（Service 层调用 Dao 层）实现逻辑分离。数据库事…...
Baklib内容中台赋能资源管理升级
内容中台驱动管理升级 在数字化转型进程中，企业级内容管理工具的效能直接影响资源协同效率。以全渠道资源整合为核心的内容中台，通过集中化处理文档、FAQ及社区论坛等非结构化数据，有效解决信息孤岛问题。例如，某金融集团通过部署…...
数据结构（九）——排序
一、排序的基本概念 1.排序：重新排列表中的元素，使表中的元素满足按关键字有序 2.稳定性：Ri和Rj相对位置保持不变 3.内部排序：指在排序期间元素全部存在内存中的排序（比较和移动），如插入排序…...
)
MinerU安装(pdf转markdown、json)
在Windows上安装MinerU，参考以下几个文章，可以成功安装，并使用GPU解析。 整体安装教程： MinerU本地化部署教程——一款AI知识库建站的必备工具 其中安装conda的教程： 一步步教你在 Windows 上轻松安装 Anaconda以及使…...
Spring框架核心技术深度解析：JDBC模板、模拟转账与事务管理
一、JDBC模板技术：简化数据库操作 在传统JDBC开发中，繁琐的资源管理和重复代码一直是开发者的痛点。Spring框架提供的 JDBC模板（JdbcTemplate) 彻底改变了这一现状，它通过封装底层JDBC操作，让开发者仅需关注SQL逻辑&a…...
LCD电视LED背光全解析：直下式 vs 侧光式、全局调光 vs 局部调光与HDR体验
Abstract: This article explores the various types of LED backlighting used in televisions and monitors. It categorizes backlight systems based on structural design—direct-lit and edge-lit—as well as by dimming technology—global dimming and local dimmin…...