【数据结构】LRU缓存的简单模拟实现(leetcode力扣146LRU缓存)

文章目录

  • 一、定义
  • 二、LRU模拟实现
  • 二、代码实现


一、定义

LRU是Least Recently Used的缩写,意思是最近最少使用,它是一种Cache替换算法。
Cache的容量有限,因此当Cache的容量用完后,而又有新的内容需要添加进来时, 就需要挑选并舍弃原有的部分内容,从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用的内容替换掉。

二、LRU模拟实现

146.LRU缓存
示例:pandas 是基于NumPy 的一种工具,该工具是为了解决数据分析任务而创建的。

下面我们就借力扣的这道题来简单实现一个

题目中要求我们以O(1)的时间复杂度来完成,查找的话我们首先肯定会想到哈希表,但又涉及一个问题,我们查找完之后还需要更新一下刚刚查找数据的位置,将这个数据置为是新的数据,我们如何解决查找完改变数据的标识也做到O(1)呢?

要保持高效实现O(1)的put和get,那么使用双向链表和
哈希表的搭配是最高效和经典的
。使用双向链表是因为双向链表可以实现任意位置O(1)的插入和删除,使用哈希表是因为哈希表的增删查改也是O(1)。
在这里插入图片描述

需要注意:这里最巧的设计就是将unordered_map的value type放成list<pair<int, int>>::iterator,因为这样,当get一个已有的值以后,就可以直接找到key在list中对应的iterator,然后将这个值移动到链表的头部,保持LRU。

二、代码实现

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<list>
#include<unordered_map>

using namespace std;


class LRUCache {

public:
	LRUCache(int capacity)
		:_capacity(capacity)
	{}

	int get(int key) {
		
		auto ret = _hashMap.find(key);
		//在hash中找到了key存的地方
		if (ret != _hashMap.end()) {
			LtIter it = ret->second;

			//将it移动到_LRUList的头部
			_LRUList.splice(_LRUList.begin(), _LRUList, it);
			return it->second;
		}
		else {
			return -1;
		}
	}

	void put(int key, int value) {
		auto ret = _hashMap.find(key);

		//原来没有key的数据则添加
		if (ret == _hashMap.end()) {

			//LRU满了,删除最近最少使用的就是链表尾部
			if (_capacity == _hashMap.size()) {
				pair<int, int>back = _LRUList.back();

				_hashMap.erase(back.first);//删哈希里面
				//链表里面k存的和哈希的是同一个key
				_LRUList.pop_back();//删链表尾部
			}
			//放入新的数据到链表头部
			_LRUList.push_front(make_pair(key, value));
			//哈希表中添加
			_hashMap[key] = _LRUList.begin();
		}

		//原来有key的数据则更新
		else {
			LtIter it = ret->second;
			it->second = value;
			//将这个位置移到链表头部
			_LRUList.splice(_LRUList.begin(), _LRUList, it);
		}
	}

private:
	//链表存kv结构
	//k为key值,v为我们要更新的数据
	typedef list<pair<int, int>>::iterator LtIter;//重命名链表迭代器

	int _capacity; // 容量大小,超过容量则换出,保持LRU
	//_LRUList假设链表头部为最近使用的,尾部为最近最少使用
	list<pair<int, int>> _LRUList;
	//hash中存放的是key值与对应链表迭代器的的映射关系
	unordered_map<int, LtIter>_hashMap;
 };

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

在Android中使用Flow获取网络连接信息

在Android中使用Flow获取网络连接信息 如果你是一名Android开发者&#xff0c;你可能会对这个主题感到有趣。考虑到几乎每个应用程序都需要数据交换&#xff0c;例如刷新动态或上传/下载内容。而互联网连接对此至关重要。但是&#xff0c;当用户的设备离线时&#xff0c;数据如…

天啦撸 超级麻烦的MySQL索引和数据引擎,快拿小本本记好

1 MySQL的索引 1.1 索引 定义&#xff1a; 索引是一个排序的列表&#xff0c;包含索引字段的值和其对应的行记录的数据所在的物理地址 ●索引是一个排序的列表&#xff0c;在这个列表中存储着索引的值和包含这个值的数据所在行的物理地址&#xff08;类似于C语言的链表通过…

使用Maven Archetype插件制作项目脚手架(一)

Archetype是一个Maven项目模板工具包。通过Archetype我们可以快速搭建Maven项目。比如我们在ide里面创建项目时&#xff0c;可以选择很多maven内置的Archetype&#xff0c;我们最常用的可能是maven-archetype-quickstart 当然maven提供了能力&#xff0c;让我们自定义项目结构&…

Electron自定义通知Notification

Notification是什么&#xff1f; 对于渲染进程&#xff0c;Electron 允许开发者使用通知中API&#xff0c;来运行系统的原生通知进行显示。 如何实现系统Notification&#xff1f; const { Notification } require(electron);const isAllowed Notification.isSupported();…

最新ChatGPT商业运营网站程序源码,支持Midjourney绘画,GPT语音对话+DALL-E3文生图+文档对话总结

一、前言 SparkAi创作系统是基于ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统&#xff0c;支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美&#xff0c;可以说SparkAi是目前国内一款的ChatGPT对接OpenAI软件系统。那么如何搭建部署AI创作Ch…

【FPGA】分享一些FPGA高速信号处理相关的书籍

在做FPGA工程师的这些年&#xff0c;买过好多书&#xff0c;也看过好多书&#xff0c;分享一下。 后续会慢慢的补充书评。 【FPGA】分享一些FPGA入门学习的书籍【FPGA】分享一些FPGA协同MATLAB开发的书籍 【FPGA】分享一些FPGA视频图像处理相关的书籍 【FPGA】分享一些FPGA高速…

【【IIC模块Verilog实现---用IIC协议从FPGA端读取E2PROM】】

IIC模块Verilog实现–用IIC协议从FPGA端读取E2PROM 下面是 design 设计 I2C_dri.v module IIC_CONTROL #(parameter SLAVE_ADDR 7b1010000 , // E2PROM 从机地址parameter CLK_FREQ 26d50_000_000 , // 50MHz 的时钟频率parameter …

[内功修炼]函数栈帧的创建与销毁

文章目录 1:什么是函数栈帧2:理解函数栈帧能解决什么问题呢3:函数栈帧的创建与销毁的解析3.1:什么是栈3.2:认识相关寄存器与汇编指令相关寄存器相关汇编指令 3.3 解析函数栈帧的创建和销毁3.3.1 预备知识3.3.2 详细解析一:调用main函数,为main函数开辟函数栈帧First:push前push…

【Python3】\u字符与中文字串互转

小水。 encode和decode&#xff1a; str没有decode函数&#xff0c;但对应的有encode函数&#xff0c;该函数作用是转码为bytes对象bytes通过decode函数转换回对应的str对于一些偏激的(可以用过分来形容)的字符串&#xff0c;例如一二三\\u56db\\u4e94\\u516d&#xff0c;是有…

k8s 组件

k8s: kubernets:8个字母省略&#xff0c;就是k8s. 自动部署&#xff0c;自动扩展和管理容器化的应用程序的一个开源系统。 k8s是负责自动化运维管理多个容器化程序的集群&#xff0c;是一个功能强大的容器编排工具。 以分布式和集群化的方式进行容器管理。 1.20面试版本 …

RPC(6):RMI实现RPC

1RMI简介 RMI(Remote Method Invocation) 远程方法调用。 RMI是从JDK1.2推出的功能&#xff0c;它可以实现在一个Java应用中可以像调用本地方法一样调用另一个服务器中Java应用&#xff08;JVM&#xff09;中的内容。 RMI 是Java语言的远程调用&#xff0c;无法实现跨语言。…

小程序真机如何清除订阅数据

在做小程序订阅消息开发的过程中发现&#xff0c;真机上如果是选择了‘总是保持以上选择’&#xff0c;一旦用户授权后&#xff0c;后面就不会再弹出申请改订阅消息的授权弹窗&#xff0c;这对于开发过程中是很不方便的。 曾试过清除缓存&#xff0c;重进小程序也不能清除掉 解…

爬虫反爬之代码混淆,特殊编码,表情编码

不知道你是否见过这样的代码&#xff0c;完全看不懂。 大家好&#xff0c;这一集我们来看一下前端反爬的代码混淆&#xff0c;一般啊我们自己写的前端代码都是直接上传公开的&#xff0c;如果用的不是框架打包出来的代码&#xff0c;就是自己写的js&#xff0c;html文件没有经过…

T-Dongle-S3开发笔记——创建工程

创建Hello world工程 打开命令面板 方法1&#xff1a;查看->命令面板 方法2&#xff1a;按F1 选择ESP-IDF:展示示例项目 创建helloworld 选择串口 选择芯片 至此可以编译下载运行了 运行后打印的信息显示flash只有2M。但是板子上电flash是W25Q32 4MB的吗 16M-bit

SPFA算法总结

知识概览 SPFA算法是Bellman_Ford算法的优化。时间复杂度一般是O(m)&#xff0c;最坏时间复杂度是O(nm)&#xff08;遇到网格图、菊花图&#xff09;&#xff0c;其中n是点数&#xff0c;m是边数。SPFA算法其实是单源最短路限制最小的算法&#xff0c;只要图中没有负环&#xf…

Mongodb基础介绍与应用场景

NoSql 解决方案第二种 Mongodb MongoDB 是一款开源 高性能 无模式的文档型数据库 当然 它是NoSql数据库中的一种 是最像关系型数据库的 非关系型数据库 首先 最需要注意的是 无模式的文档型数据库 这个需要后面我们看到它的数据才能明白 其次是 最像关系型数据库的非关系型数据…

通过three.js玩转车展项目

1.项目搭建 1.1 创建文件夹 mkdir 文件名1.2 初始化package.json npm init -y1.3 安装打包工具并配置相关依赖 npm i parcel -d在package.json中打包路径和指令 1.4 安装three.js npm i three -d2.项目搭建 2.1 新建index.html&#xff0c;并再index.html引入car.js,在…

2023版本QT学习记录 -6- UDP通信之UDP接收端

———————UDP接收端——————— &#x1f384;动图演示 &#x1f384;发送端通信步骤思维导图 &#x1f384;添加组件 QT core gui network&#x1f384;添加头文件 #include "qudpsocket.h"&#x1f384;创建接收对象 QUdpSocket *recvsocket;&…

在VSCode中使用Git教程

文章目录 提交代码操作分支提交远程库拉取代码参考 介绍一下如何在VSCode中使用Git 首先在VSCode中打开一个项目 打开项目后, 点击下图按钮, 可以引入Git 提交代码 点击 &#xff1b;相当于git add. 下面两张图, 第一张表示改文件后的号, 只会add本文件. 第二张图表示这段时…

Jenkins的邮箱配置和插件下载

启动&#xff1a;java -jar jenkins.war 一定在jenkins.war的目录下 进入cmd命令 浏览器输入网址&#xff1a;http://localhost:8080/login?from%2F 账号&#xff1a;admin 密码&#xff1a;123456 安装插件&#xff1a; 插件更新后重启下 配置邮箱账号&#xff1a; 3…