LRU的实现
题目内容
实现一个 LRUCache
类,三个接口:
LRUCache(int capacity)
创建一个大小为capacity
的缓存get(int key)
从缓存中获取键为key
的键值对的value
put(int key, int value)
向缓存中添加键值对(key, value)
要求 get
和 put
的均摊时间复杂度为 O ( 1 ) O(1) O(1)
题解
对于 get
操作,我们需要快速获取到 key
对应的键值对,哈希表可以解决。
对于 put
操作,我们需要快速 put
一个键值对,也可以用哈希表解决。
但是问题在于,我们 get
和 put
时,需要维护键值对最近使用的情况。
这部分我们可以用双向链表维护,每次操作一个键值对时,将其从原来链表的位置中移除,重新添加到链表头。定义链表头的数据是最近一次使用的,链表尾是最近最少使用的。
对于哈希表,键可以为 key
,映射到一个链表结点 LRUNode
,LRUNode
中包括前后链表结点,以及当前链表结点的 key
和 value
。
为什么我们要在链表结点中存储
key
呢,直接看上去没什么用。
考虑我们需要利用 LRU 策略从缓存中弹出一个最近最少使用的结点。
根据我们的定义,链表尾的结点是最近最少使用的,除了要将其从链表中移除,还需要将其从哈希表中移除,而从哈希表中移除需要使用key
,这才是链表结点中存储key
的原因。
定义LRU中的链表结点 LRUNode
。
struct LRUNode {LRUNode* prev;LRUNode* next;int key;int val;LRUNode(int key, int val): key(key), val(val), prev(nullptr), next(nullptr) {}
};
对于 LRUNode
,其会从链表中被移除,也会被添加到链表,所以需要实现这两个方法
void removeLRUNodeFromLinklist(LRUNode* node) {node->prev->next = node->next;node->next->prev = node->prev;
}void insertLRUNodeToLinklist(LRUNode* node) {node->next = head->next;head->next->prev = node;head->next = node;node->prev = head;
}
对于 LRUNode
,其会从哈希表 key2LRUNode
中被移除,也会被添加到哈希表 key2LRUNode
,所以需要实现这两个方法
void removeLRUNodeFromHashTable(LRUNode* node) {if (!key2LRUNode.count(node->key)) return;key2LRUNode.erase(node->key);
}void insertLRUNodeToHashTable(LRUNode* node) {key2LRUNode[node->key] = node;
}
接下来实现 get
的逻辑
int get(int key) {// key 不存在if (!key2LRUNode.count(key)) return -1;// 取出 key 对应的 LRUNodeLRUNode* node = key2LRUNode[key];// 当前 LRUNode 是最近一次使用的,将其放到链表头removeLRUNodeFromLinklist(node);insertLRUNodeToLinklist(node);return node->val;
}
继续实现 put
的逻辑
void put(int key, int value) {// 如果不存在 key ,则需要新建该键值对if (!key2LRUNode.count(key)) {// 缓存已满,要从缓存中通过LRU策略弹出最近最少使用的LRUNodeif (size_ >= capacity_) {// 链表尾即最近最少使用的LRUNode* node = tail->prev;// 从链表中删去removeLRUNodeFromLinklist(node);// 从哈希表中删去removeLRUNodeFromHashTable(node);// 释放 node 的内存空间,如果是智能指针就不需要手动释放了delete node;// 释放一个空间size_ -= 1;}// 创建一个新的 LRUNodeLRUNode* newLRUNode = new LRUNode(key, value);// 添加到链表中insertLRUNodeToLinklist(newLRUNode);// 添加到哈希表中insertLRUNodeToHashTable(newLRUNode);size_ += 1;} else {// 获取到 key 对应的已存在于缓存中的 LRUNode 节点LRUNode* node = key2LRUNode[key];// 更新键值对的权值node->val = value;// 从链表中删去removeLRUNodeFromLinklist(node);// 添加到链表中insertLRUNodeToLinklist(node);// 添加到哈希表中,其实这步是不需要的,因为哈希表对应的是 LRUNode 的地址insertLRUNodeToHashTable(node);// 这里只是 key 对应的 value 修改了,size_ 不变}
}
相关文章:
LRU的实现
题目内容 实现一个 LRUCache 类,三个接口: LRUCache(int capacity) 创建一个大小为 capacity 的缓存get(int key) 从缓存中获取键为 key 的键值对的 valueput(int key, int value) 向缓存中添加键值对 (key, value) 要求 get 和 put 的均摊时间复杂度…...
consul 备份还原导入导出
正文 工作中要保证生产环境部署的consul的集群能够安全稳定地对外提供服务,即使出现系统故障也能快速恢复,这里将讲述部分的备份还原操作及KV的导入导出操作。 备份与还原 配置文件、服务器状态 需要备份的主要有两类数据:consul相关的配置文…...
6.网络编程套接字(下)
文章目录 4.TCP流套接字编程4.1ServerSocket API4.2Socket API4.3TCP中的长短连接4.4示例一:一发一收(长连接)4.4.1TCP服务端4.4.2TCP客户端 4.5示例二:请求响应(短连接)4.5.1TCP服务端4.5.2TCP客户端 4.6再…...
4.3-内置后置PostProcess处理器深度讲解
在reader里面注册了很多Bean定义 reader会调取register()来注册配置类 调用上句,就会把配置类注册到BeanDefinitionMap中去 配置类有了、解析配置类的处理器有了 然后, 在第三步refresh() 进行IOC容器刷新中的invokeBeanPostProcessors(beanFactory…...
LeetCode(力扣)45. 跳跃游戏 IIPython
LeetCode45. 跳跃游戏 II 题目链接代码 题目链接 https://leetcode.cn/problems/jump-game-ii/description/ 代码 class Solution:def jump(self, nums: List[int]) -> int:if len(nums) 1:return 0curdis 0nextdis 0step 0for i in range(len(nums)):nextdis max(…...
mysql5.8 免安装版(压缩包)win10 安装
目录 1、下载MySQL5.82、如何安装、配置my.ini配置注意 3初始化mysql3.1. 初始化mysql3.2. 安装mysql服务3.3. 启动mysql3.4. 登录mysql3.5. 修改root密码3.6. 配置远程连接 Mysql5.8安装踩坑记录,推荐使用Docker安装,我是电脑虚拟化可能会蓝屏没用这个功…...
STM32-HAL库06-硬件IIC驱动FM24CL16B非易失存储器
STM32-HAL库06-IIC驱动FM24CL16B非易失存储器 一、所用材料: STM32VGT6自制控制板 STM32CUBEMX(HAL库软件) MDK5 二、所学内容: 通过HAL库的硬件IIC对FM24CL16B存储器进行写与读取操作。 三、CUBEMX配置: 第一步…...
python-wordcloud词云
导入模块 from wordcloud import WordCloud import jieba import imageio import matplotlib.pyplot as plt from PIL import ImageGrab import numpy as npwordcloud以空格为分隔符号,来将文本分隔成单词 PIL pillow模块 img imageio.imread(image.png)这行代码…...
单元测试与自测
单元测试在百度百科的定义: 自测在百度百科的定义: 单元测试是测一个类或一个函数,自立门第main函数,不依赖于项目,预期的是这个类或函数是没有问题的。程序编码完成之后至各种测试再到用户使用出现的任何bug都是单元测…...
2023-09-12 LeetCode每日一题(课程表 IV)
2023-03-29每日一题 一、题目编号 1462. 课程表 IV二、题目链接 点击跳转到题目位置 三、题目描述 你总共需要上 numCourses 门课,课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite ,其中 prerequisites[i] [ai, bi] 表示如果你…...
RabbitMQ基础
目录 MQ MQ概述 MQ 的优势 1.应用解耦 2.异步提速 3.削峰填谷 MQ 的劣势 1.系统可用性降低 2.系统复杂度提高 3.一致性问题 使用 MQ 需要满足什么条件呢? RabbitMQ 简介 编辑RabbitMQ 中的相关概念 RabbitMQ 提供了 6 种工作模式 JMS java实现Ra…...
ITIL 4—创建、交付和支持—创建、交付和支持服务的价值流
4. 创建、交付和支持服务的价值流 本章节提供了有关如何: 记录一个价值流以理解工作流程如何贯穿该组织了解创建一个新服务的原型价值流了解支持一个现场服务的原型价值流 本章将帮助从业者理解: 价值流在 服务价值系统(SVS) 中的作用价值流的分类如…...
微信怎么给自己发消息
前段时间看到一份数据调查,说是到目前为止,全球使用微信的用户已达到10亿多人次,天啊,多么强大的用户群体! 这么多人喜欢使用微信,相信大家都知道,微信里面有一个特俗功能,可以自己…...
正交试验设计法
正交实验设计 一、什么是正交试验设计法? 是一种成对测试交互的系统的统计方法。它提供了一种能对所有变量对的组合进行典型覆盖(均匀分布)的方法。 可以从大量的试验点中挑出适量的、有代表性的点,利用“正交表”,…...
Scrum工具:助力快速迭代和高效交付
随着软件开发行业的不断发展,敏捷开发方法逐渐成为了主流。Scrum作为敏捷开发中最具代表性的工具之一,其在流程设计、团队协作以及项目管理等方面发挥着重要作用。本文将深入探讨Scrum的优势以及如何运用Scrum提升团队效率与质量。 一、Scrum敏捷开发工…...
通过Python行命令搭建HTTP服务器结合内网穿透实现外网访问
文章目录 1.前言2.本地http服务器搭建2.1.Python的安装和设置2.2.Python服务器设置和测试 3.cpolar的安装和注册3.1 Cpolar云端设置3.2 Cpolar本地设置 4.公网访问测试5.结语 1.前言 Python作为热度比较高的编程语言,其语法简单且语句清晰,而且python有…...
Android T 窗口层级其三 —— 层级结构树添加窗口
文章目录 序节点添加Task以DefaultTaskDisplayArea为父节点以Task为父节点 ActivityRecordWindowTokenWindowState以WindowToken为父节点以ActivityRecord为父节点 小结调用场景添加差异 流程分析添加log堆栈打印流程LauncherStatusBar 序 尚未添加窗口的层级结构树࿰…...
3D虚拟数字人定制,推动传统文化传播新高度
“数字人”成为“汉语盘点2022”年度十大新词语。伴随着科技发展成长的年轻人逐渐成为消费主力军,如何在虚拟世界与年轻一代用户互动以抓住95后年轻人受众,成为不少传统文化品牌发力的重点。 数字人“天妤”,在3D虚拟数字人定制中࿰…...
kubernetes进阶 (三) 基础练习
前两天朋友给了我几道题,看着挺简单的,但实际做的时候发现坑不少,这里做下笔记 一、镜像构建部署lnmp 1、构建镜像 nginx、php、mysql 要求使用centos7作为基础镜像 2、使用deployment部署上面的容器,要求3个服务要放到一个pod中(虽然这样是…...
数据结构 排序
目录 第八章 排序8.1排序的基本概念1. 概念2. 排序算法的分类 8.2 插入排序8.2.1 直接插入排序8.2.2 算法效率分析8.2.2 折半插入排序总结8.2.3 希尔排序 8.3 交换排序8.3.1冒泡排序8.3.2快速排序(了解栈的过程) 8.4 选择排序8.4.1 简单选择排序8.4.2 堆…...
Cpp/Qtday050912cpp基础
目录 实现一个图形类(Shape),包含受保护成员属性:周长、面积, 公共成员函数:特殊成员函数书写 定义一个圆形类(Circle),继承自图形类,包含私有属性&#x…...
Git diff 使用 vimdiff 对比差异
在Ubuntu中使用Git时,可使用命令行的git diff命令来对比两次提交的差异,但是这种对比查看方式无法直观地查看修改的差异,在对比和查看时不太方便。 可以使用vimdiff作为Git diff的对比工具,这样就方便了许多,Git的配置…...
c小白勇闯结构体!!!!
目录 1.结构体类型的声明 1.结构的基础 2.结构体的声明 3.结构体成员的类型 4结构体变量的定义和初始化 2.结构体成员的访问 3.结构体传参 1.结构体类型的声明 1.结构的基础 结构是一些值的集合,这些值称为成员变量。结构的每个成员可以是不同类型的变量 结构体变量的创…...
【DevOps核心理念基础】3. 敏捷开发最佳实践
一、敏捷开发最佳实践 1.1 项目管理 1.2 需求管理 1.3 技术架构 1.4 技术开发 1.5 测试 二、敏捷开发最佳实践 2.1 敏捷开发的执行细节 三、全面的DevOps工具链 四、版本控制和协作开发工具 4.1 集中式版本控制工具 4.2 分布式版本控制工具 一、敏捷开发最佳实践 …...
二进制、数位dp:0912T3
考虑题目转化,二进制下满足 i ⊆ j , ( i x ) ⊆ ( j y ) i\subseteq j,(ix)\subseteq (jy) i⊆j,(ix)⊆(jy) 这显然是个数位dp形式 考虑枚举每一位与进位, d p k , p 1 , p 2 dp_{k,p_1,p_2} dpk,p1,p2 表示第 k − 1 k-1 k−1 位向第 k k…...
Java基于SpringBoot+Vue的 4S店车辆管理系统
博主介绍:✌程序员徐师兄、7年大厂程序员经历。全网粉丝30W,Csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 文章目录 1 简介2 技术栈3 功能总览4 系统设计4.1 系统设计主要功能4.2 数据库设计4.2.1 数据库设计规范4.2…...
助力智能化公路养护,基于YOLOv5s集成SPD-BIFPN-SE开发构建公路开裂检测识别系统
在前文中我们尝试构建了在隧道、涵洞尝尽下的自动智能化养护巡查相关的模型,进行了实地测试评估,感兴趣的话可以自行移步阅读即可: 《基于轻量级YOLOv5s开发构建隧道基建裂痕、脱落等缺陷问题检测系统》 本文的想法是相近的,核心…...
C++--day5
实现一个图形类(Shape),包含受保护成员属性:周长、面积, 公共成员函数:特殊成员函数书写 定义一个圆形类(Circle),继承自图形类,包含私有属性:半…...
Django应用部署实战:从开发到生产,全程解析
部署架构图 版本说明 Centos 7.4 Python 3.6.4 Django 2.0.2 Channels 2.0.0 MySql 5.7 uWSGI Nginx 1.12.2 部署前 1、更新系统环境 yum install epel-release 2、安装所有的开发工具包 yum groupinstall -y “Development tools” 一、安装python 3.6.4 1、下载 cd /usr/…...
群晖NAS如何在内网部署HTTPS服务让浏览器信任证书
前言 最近在折腾内部部署Web服务。通过Vue实现一个H5的内部的管理服务。但在实际部署过程中由于种种原因,必须部署成Https服务。但在部署成Https服务后,由于没有HTTPS证书,每次进入页面都会被浏览器拦截。使用起来非常不便。于是开始各种Goo…...
做动画人设有哪些网站可以借鉴/营销策略分析
这种组合方式,依赖的是JUnit和Spring容器,进行对象注入,而Mockit的作用是在spring生成的bean中,注入mock对象。相当于使用了Mockito的一部分功能。1、首先导入包:<dependencies>2、被测试类production-class&…...
网站开发与设计静态网页源代码/项目优化seo
1、日志简介nginx日志主要有两种:访问日志和错误日志。访问日志主要记录客户端访问nginx的每一个请求,格式可以自定义;错误日志主要记录客户端访问nginx出错时的日志,格式不支持自定义。两种日志都可以选择性关闭。 通过访问日志&…...
帮人做兼职的网站吗/北京建站
排序和搜索是数据结构和算法学习中的两个最基本的操作。关于排序,我在上一篇已经做了比较详细的介绍,请参考 http://www.cnblogs.com/chenxizhang/archive/2009/04/22/1441209.html 这一篇我们来关注一下搜索。我们同样把目光放在Array这个最基础的数据类…...
建设网站需要体现的流程有哪些内容/seo整站优化什么价格
这里收集了一些java面试题的链接; http://blog.csdn.net/jackfrued/article/details/44921941 原文来自:http://www.cnblogs.com/xdp-gacl/p/3641769.html 1、一个".java"源文件中是否可以包括多个类(不是内部类)&#…...
张家港高端网站建设公司/临安网站seo
轻量级网络之GhostNet前言动机Ghost模块G-bneckGhostNet网络结构实验性能消融实验Ghost模块 pytorch代码欢迎交流,禁止转载!!前言 《GhostNet: More Features from Cheap Operations》 论文地址:GhostNet: More Features from Ch…...
网站建设2017国内排行/网站推广公司大家好
基于你说的情况,我只是猜想的是,肯定是报错了,不然定时任务不会无缘无故停下,只是呢,这个报错你们没有发现罢了你们run方法里应该有一些异常Exception捕获,但是没有捕获错误,也就是Error&#x…...