leetcode LRU 缓存

leetcode: LRU 缓存

LRU 全称为 Least Recently Used,最近最少使用,常常用于缓存机制,比如 cpu 的 cache 缓存,使用了 LRU 算法。LRU 用于缓存机制时,关键的是当缓存满的时候有新数据需要加载到缓存的,这个时候需要淘汰谁的问题。

如下图所示,表示 LRU 算法的过程。假如有一个缓存,共有 4 个存储空间,按访问时间进行排序,最左边的存储空间存储的是最近访问的数据,最右边的存储空间存储的是最长时间没有访问的数据。

(1)一开始,缓存是空的,这个时候向缓存中放入一个数据 100,100 放到最左边的存储空间

(2)向缓存中放入一个数据 50,此时缓存有空余空间,所以将已有的数据向后移动,将 50 放到缓存的最左边

(3)向缓存中放入数据 500, 步骤与上一步相同

(4)向缓存中放入数据 1000,步骤与上一步相同

(5)读取数据 100,读取之后 100 就是最后访问的数据了,所以将 100 移到缓存的最左边,其它数据依次向后移动

(6)向缓存中放入数据 1,此时缓存是满的,所以需要先淘汰一个数据,从访问时间来看,最后一次访问 50 的间隔时间最长,也就是排在最右边的数据,所以将 50 淘汰,其它数据向后移动,将新数据 1 放入最左边的位置

如下是题目描述,题目的最后要求 get() 和 put() 的时间复杂度都要是 O(1) 的。使用数组来表示缓存难以满足 O(1) 的要求,因为在 put 或者 get 的时候,会引起数组数据的移动,数组中数据的移动时间复杂度是 O(n) 的。所以需要使用链表来表示缓存,当访问一个数据的时候需要将当前这个数据从原来的位置上删除,然后加到链表的头部,删除一个节点的话,需要将这个节点的前一个节点和下一个节点连接起来,如果使用单向链表的话,那么只能找到这个节点的下一个节点,找不到上一个节点,所以需要使用双向链表。

 

(1)使用双向循环链表来表示缓存

(2)为了满足时间复杂度是 O(1) 的要求,使用 data_addr_ 数组来保存节点的地址,数组的下标是 key,题目中说明了 key 的取值范围是 [0, 10000],所以可以使用一个数组来表示。使用 map 也不能保证时间复杂度是 O(1) 的,map 一般使用红黑树来实现,时间复杂度是 O(logn) 的。把数组的下标当 key,数组元素的值就是值,数组本省也可以当做一个简单的 map 来使用。

(3)当 put 数据时,要进行判断现在缓存是不是满了,如果满的话需要删除最久没有访问的数据,head_->next 保存最新访问的数据,head_->prev 保存最久没有访问的数据

struct Node {int key;int value;struct Node *next;struct Node *prev;
};class LRUCache {
public:LRUCache(int capacity) {capacity_ = capacity;head_ = new Node();head_->next = head_;head_->prev = head_;}int get(int key) {Node *node = data_addr_[key];if (node == nullptr) {return -1;}ListUnLink(node);ListLinkHead(node);return node->value;}void put(int key, int value) {if (data_addr_[key] != nullptr) {       Node *node = data_addr_[key];ListUnLink(node);node->value = value;ListLinkHead(node);} else {Node *new_node = new Node();new_node->key = key;new_node->value = value;new_node->next = nullptr;new_node->prev = nullptr;if (count_ == capacity_) {Node *to_delete = head_->prev;ListUnLink(to_delete);data_addr_[to_delete->key] = nullptr;delete to_delete;count_--;}ListLinkHead(new_node);data_addr_[key] = new_node;count_++;}}void ListLinkHead(struct Node *ele) {ele->next = head_->next;ele->next->prev = ele;head_->next = ele;ele->prev = head_;}void ListUnLink(struct Node *ele) {ele->prev->next = ele->next;ele->next->prev = ele->prev;}private:int capacity_ = 0;int count_ = 0;Node *data_addr_[10001] = {nullptr};struct Node *head_ = nullptr;};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/352691.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

streamlit markdown里支持latex公式显示

参考: https://docs.streamlit.io/develop/api-reference/write-magic/st.write https://discuss.streamlit.io/t/streamlit-markdown-a-streaming-markdown-component-with-latex-mermaid-table-code-support/72187 也有独立支持的st.latex 接口单独显示公司&…

Python 引入中文py文件

目录 背景 思路 importlib介绍 使用方法 1.导入内置库 importlib.util 2.创建模块规格对象 spec importlib.util.spec_from_file_location("example_module", "example.py") 3.创建模块对象 module importlib.util.module_from_spec(spec) …

远程工作岗位机会

电鸭:​​​​​​https://eleduck.com/?sortnew电鸭社区是具有8年历史的远程工作招聘社区,也是远程办公互联网工作者们的聚集地。在社区,我们进行有价值的话题讨论,也分享远程、外包、零活、兼职、驻场等非主流工作机会。「只工…

从客户端WebAPI视角下解读前端学习

API 应用程序接口(API,Application Programming Interface)是基于编程语言构建的结构,使开发人员更容易地创建复杂的功能。它们抽象了复杂的代码,并提供一些简单的接口规则直接使用。 JavaScript VS 客户端 API VS 客…

麒麟Kylin | 操作系统的安装与管理

以下所使用的环境为:VMware Workstation 17 Pro、Kylin-Server-10-SP2-x86-Release-Build09-20210524 一、创建虚拟机 在VMware主机单击【创建新的虚拟机】 **在新建虚拟机向导中选择【自定义】,然后点击【下一步】 ** 保持默认选项,然后…

elasticsearch hanlp插件远程词典配置

elasticsearch hanlp插件远程词典配置 背景远程词典配置新增远程词典文件修改hanlp-remote.xml自动加载词典 远程词典测试 背景 在使用elasticsearch的过程中,总会遇到与分词相关的需求,这里将针对常用的elasticsearch hanlp(后面统称为 es …

SpringBoot三层架构

目录 一、传统方式 二、三层架构 三、代码拆分 1、dao层 2、service层 3、control层 四、运行结果 一、传统方式 上述代码存在一定的弊端,在进行软件设计和软件开发中提倡单一责任原则,使代码的可读性更强,复杂性更低,可扩展性…

毕业答辩PPT:如何在短时间内高效准备?

提起PPT,大家的第一反应就是痛苦。经常接触PPT的学生党和打工人,光看到这3个字母,就已经开始头痛了: 1、PPT内容框架与文案挑战重重,任务艰巨,耗费大量精力。 2、PPT的排版技能要求高,并非易事…

R语言统计分析——数据集概念和数据结构

参考资料:R语言实战.第2版 1、数据集的概念 数据集通常是由数据构成的一个矩形数组,行表示观测,列表示变量。 不同行业对于数据集的行和列叫法不同。统计学称为观测(observation)和变量(variable&#xff…

mysql数据库中触发器的使用

一、修改分隔符号 delimiter $$或者是//或者~~都行 二、创建触发器函数名称 create trigger 函数名 三、什么样的操作出发,操作那个表 after:.....之后触发 befor:.....之前触发 insert: 插入触发 update:修改被触发 d…

什么是隐马尔可夫模型?

文章目录 一、说明二、玩具HMM:5′拼接位点识别三、那么,隐藏了什么?四、查找最佳状态路径五、超越最佳得分对齐六、制作更逼真的模型七、收获 关键词:hidden markov model 一、说明 被称为隐马尔可夫模型的统计模型是计算生物学…

gridview自带编辑功能如何判断用户修改的值的合法性

在使用GridView的编辑功能更新值时,确保输入的值合法性是十分重要的。为了实现这一点,你可以在GridView的RowUpdating事件中加入代码来检查用户输入的值。如果发现输入的值不合法,你可以取消更新操作并向用户显示错误消息。下面是如何实现的步…

05眼动识别软件详情2波形优化-滤波

对应视频链接点击直达 01项目点击下载,可直接运行(含数据库) 05眼动识别软件详情2 对应视频链接点击直达期望的数据展示数据波形对比如何实现几种常用滤波介绍维纳滤波巴特沃斯滤波器中值滤波排序滤波 推荐 结语其他以下是废话 原始数据的波…

CorelDRAW Graphics Suite下载2024最新版-CorelDRAW2024详细安装步骤

CorelDRAW​​ Graphics Suite官方版是款很多用户在工作中都会使用的矢量图形设计工具。CorelDRAW Graphics Suite正式版采用量身定制的界面和无与伦比的定制功能,畅享无缝设计经验。并且CorelDRAW Graphics Suite还可以广泛应用于商标设计、标志制作、模型绘制、插…

华为手环9省电设置

1、 手环开启熄屏显示续航约3天,原因为屏幕持续常亮显示;如不需要可通过手环“设置->表盘->熄屏显示”路径进行关闭; 2、 手环具备后台健康自动检测功能,您可根据需要选择是否使用或关闭: (1&#x…

AI发展面临的问题? —— AI对创造的重新定义

一、AI的问题描述 AI与数据安全问题:随着AI技术的发展和应用,数据安全问题日益突出。AI模型训练依赖于大量数据,而这些数据中可能包含个人隐私、商业秘密等敏感信息。如果数据在采集、存储、使用过程中处理不当,可能导致数据泄露或…

大数据的力量:推动战略决策和业务转型

在当前全球化的时代背景下,国际间的联系日益紧密,世界变得更加互联互通。面对各种危机,数据驱动决策和分析显得愈发重要。从医学研究到市场趋势分析,大数据技术在各个领域发挥着关键作用,推动着一场深刻的变革浪潮。 大…

Unity API学习之资源的动态加载

资源的动态加载 在实际游戏开发的更新换代中&#xff0c;随着开发的软件不断更新&#xff0c;我们在脚本中需要拖拽赋值的变量会变空&#xff0c;而要想重新拖拽又太花费时间&#xff0c;因此我们就需要用到Resources.Load<文件类型>("文件名")函数来在一开始…

产品应用 | 小盒子跑大模型!英码科技基于算能BM1684X平台实现大模型私有化部署

当前&#xff0c;在人工智能领域&#xff0c;大模型在丰富人工智能应用场景中扮演着重要的角色&#xff0c;经过不断的探索&#xff0c;大模型进入到落地的阶段。而大模型在落地过程中面临两大关键难题&#xff1a;对庞大计算资源的需求和对数据隐私与安全的考量。为应对这些挑…

齐普夫定律在循环神经网络中的语言模型的应用

目录 齐普夫定律解释公式解释图与公式的关系代码与图的分析结论 使用对数表达方式的原因1. 线性化非线性关系2. 方便数据可视化和分析3. 降低数值范围4. 方便参数估计公式详细解释结论 来自&#xff1a;https://zh-v2.d2l.ai/chapter_recurrent-neural-networks/language-model…