【LeetCode刷题-链表】--146.LRU缓存

146.LRU缓存

image-20231103194750082

方法一:哈希表+双向链表

使用一个哈希表和一个双向链表维护所有在缓存中的键值对

  • 双向链表按照被使用的顺序存储了这些键值对,靠近头部的键值对是最近使用的,而靠近尾部的键值对是最久使用的
  • 哈希表即为普通的哈希映射,通过缓存数据的键映射到其在双向链表中的位置

这样以来,我们首先使用哈希表进行定位,找出缓存项在双向链表中的位置,随后将其移动到双向链表的头部,即可在O(1)的时间内完成get或者put操作,具体方法如下:

  • 对于get操作,首先判断key是否存在

    • 如果key不存在,则返回-1
    • 如果key存在,则key对应的节点是最近被使用的节点,通过哈希表定位到该节点在双向链表中的位置,并将其移动到双向链表的头部, 最后返回该节点的值
  • 对于put操作,首先判断key是否存在

    • 如果key不存在,使用key和value创建一个新的节点,在双向链表的头部添加该节点,并将key和该节点添加进哈希表中,然后判断双向链表的节点数是否超出容量,如果超出容量,则删除双向链表的尾部节点,并删除哈希表中对应的项
    • 如果key存在,则与get操作类似,先通过哈希表定位,再将对应的节点的值更新为value,并将该节点移到双向链表的头部
class LRUCache {class DLinkedNode{int key;int value;DLinkedNode prev;DLinkedNode next;public DLinkedNode(){}public DLinkedNode(int _ket,int _value){key = _ket;value = _value;}}private Map<Integer,DLinkedNode> cache = new HashMap<Integer,DLinkedNode>();private int size;private int capacity;private DLinkedNode head,tail;public LRUCache(int capacity) {this.size = 0;this.capacity = capacity;//使用伪头部和伪尾部节点head = new DLinkedNode();tail = new DLinkedNode();head.next = tail;tail.prev = head;}public int get(int key) {DLinkedNode node = cache.get(key);if(node == null){return -1;}//如果key存在,先通过哈希表定位,再移到头部moveToHead(node);return node.value;}public void put(int key, int value) {DLinkedNode node = cache.get(key);if(node == null){//如果key不存在,创建一个新节点DLinkedNode newNode = new DLinkedNode(key,value);//添加进哈希表cache.put(key,newNode);//添加至双向链表的头部addToHead(newNode);++size;if(size > capacity){//如果超出容量,删除双向链表的尾部节点DLinkedNode tail = removeTail();//删除哈希表中对应的项cache.remove(tail.key);--size;}}else{//如果key存在,先通过哈希表定位,再修改value,并移到头部node.value = value;moveToHead(node);}}private void addToHead(DLinkedNode node){node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;}private void removeNode(DLinkedNode node){node.prev.next = node.next;node.next.prev = node.prev;}private void moveToHead(DLinkedNode node){removeNode(node);addToHead(node);}private DLinkedNode removeTail(){DLinkedNode res = tail.prev;removeNode(res);return res;}}/*** 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);*/

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

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

相关文章

文心一言 VS 讯飞星火 VS chatgpt (127)-- 算法导论11.2 2题

二、用go语言&#xff0c;位向量(bit vector)是一个仅包含0和1的数组。长度为m的位向量所占空间要比包含m个指针的数组少得多。请说明如何用一个位向量来表示一个包含不同元素(无卫星数据)的动态集合。字典操作的运行时间应为 O(1)。 文心一言&#xff0c;代码正常运行&#x…

HTML5+CSS3+JS小实例:简约的黑色分页

实例:简约的黑色分页 技术栈:HTML+CSS+JS 效果: 源码: 【HTML】 <!DOCTYPE html> <html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"><meta name="viewport" content="…

【计算机网络】数据链路层——以太网协议

目录 1.完整的数据传输流程2.以太网以太网通信原理以太网帧格式MAC地址对比MAC地址和IP地址MTU 3.ARP协议ARP协议的作用ARP协议的格式ARP协议的原理 1.完整的数据传输流程 IP拥有将数据跨网络从一台主机送到另一台主机的能力&#xff0c;但IP并不能保证每次都能够将数据可靠的送…

docker中安装rabbitMq并配置启动

目录 1. 拉取镜像并安装&#xff08;此处实例安装的是最新版&#xff09;2.查看docker中已安装的镜像和版本3.启动RabbitMq4.配置管理端5.安装完成 1. 拉取镜像并安装&#xff08;此处实例安装的是最新版&#xff09; docker pull rabbitmq2.查看docker中已安装的镜像和版本 …

06、如何将对象数组里 obj 的 key 值变成动态的(即:每一个对象对应的 key 值都不同)

1、数据情况&#xff1a; 其一、从后端拿到的数据为&#xff1a; let arr [1,3,6,10,11,23,24] 其二、目标数据为&#xff1a; [{vlan_1: 1, value: 1}, {vlan_3: 3, value: 1}, {vlan_6: 6, value: 1}, {vlan_10: 10, value: 1}, {vlan_11: 11, value: 1}, {vlan_23: 23, v…

linux环境下编译,安卓平台使用的luajit库

一、下载luajit源码 1、linux下直接下载&#xff1a; a、使用curl下载&#xff1a;https://luajit.org/download/LuaJIT-2.1.0-beta3.tar.gz b、git下载地址&#xff1b;https://github.com/LuaJIT/LuaJIT.git 2、Windows下载好zip文件&#xff0c;下载地址&#xff1a;https…

银河麒麟x86版、银河麒麟arm版操作系统编译zlmediakit

脚本 # 安装依赖 gcc-c.x86_64 这个不加的话会有问题 sudo yum -y install gcc gcc-c libssl-dev libsdl-dev libavcodec-dev libavutil-dev ffmpeg git openssl-devel gcc-c.x86_64mkdir -p /home/zenglg cd /home/zenglg git clone --depth 1 https://gitee.com/xia-chu…

快速了解:什么是优化问题

1. 定义 数学优化问题是&#xff1a;在给定约束条件下&#xff0c;找到一个目标函数的最优解&#xff08;最大值或最小值&#xff09;。 2. 快速get理解 初学者对优化技术陌生的话&#xff0c;可以把 “求解优化问题” 理解为 “解一个不等式方程组”&#xff0c;解方程的。…

基于深度学习的植物识别算法 - cnn opencv python 计算机竞赛

文章目录 0 前言1 课题背景2 具体实现3 数据收集和处理3 MobileNetV2网络4 损失函数softmax 交叉熵4.1 softmax函数4.2 交叉熵损失函数 5 优化器SGD6 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; **基于深度学习的植物识别算法 ** …

Git 删除本地和远程分支

目录 删除本地和远程分支分支删除验证验证本地分支验证远程分支 开源项目微服务商城项目前后端分离项目 删除本地和远程分支 删除 youlai-mall 的 dev 本地和远程分支 # 删除本地 dev 分支&#xff08;注&#xff1a;一定要切换到dev之外的分支才能删除&#xff0c;否则报错&…

漏电继电器LLJ-100FG 电压0.38KV CT45 AC220V

LLJ-F(S)系列漏电继电器 系列型号&#xff1a; LLJ-10F(S)漏电继电器LLJ-15F(S)漏电继电器LLJ-16F(S)漏电继电器 LLJ-25F(S)漏电继电器LLJ-30F(S)漏电继电器LLJ-32F(S)漏电继电器 LLJ-60F(S)漏电继电器LLJ-63F(S)漏电继电器LLJ-80F(S)漏电继电器 LLJ-100F(S)漏电继电器LLJ-120…

教培行业的创新:微信CRM系统带来高效管理

在当今快速发展的科技环境下&#xff0c;教育培训行业面临着越来越多的挑战和机遇。如何提高管理效率、扩大市场份额、提升客户满意度&#xff0c;成为了教培行业亟待解决的问题。而微信CRM系统的出现&#xff0c;为教培行业带来了创新性的解决方案。 一些教育培训行业存在的问…

Zygote进程通信为什么用Socket而不是Binder?

Zygote进程是Android系统中的一个特殊进程&#xff0c;它在系统启动时被创建&#xff0c;并负责孵化其他应用进程。它的主要作用是预加载和共享应用进程的资源&#xff0c;以提高应用启动的速度。 在Android系统中&#xff0c;常用的进程通信方式有以下几种&#xff1a; Intent…

支付宝AI布局: 新产品助力小程序智能化,未来持续投入加速创新

支付宝是全球领先的独立第三方支付平台&#xff0c;致力于为广大用户提供安全快速的电子支付/网上支付/安全支付/手机支付体验&#xff0c;及转账收款/水电煤缴费/信用卡还款/AA收款等生活服务应用。 支付宝不仅是一个支付工具&#xff0c;也是一个数字生活平台&#xff0c;通过…

pycharm更改远程服务器地址

一、问题描述 在运行一些项目时&#xff0c;我们常需要在pycharm中连接远程服务器&#xff0c;但万一远程服务器的ip发生了变化&#xff0c;该如何修改呢&#xff1f;我们在file-settings-python interpreter中找到远程服务器&#xff0c;但是发现ip是灰色的&#xff0c;没有办…

JVM 分代垃圾回收过程

堆空间划分了代&#xff1a; 年轻代&#xff08;Young Generation&#xff09;分为 eden 和 Survivor 两个区&#xff0c;Survivor 又分为2个均等的区&#xff0c;S0 和 S1。 首先&#xff0c;新对象都分配到年轻代的 eden 空间&#xff0c;Survivor 刚开始是空的。 当 eden …

AIGC | 如何用“Flow”,轻松解决复杂业务问题

随着LLM&#xff08;大语言模型&#xff09;的爆火&#xff0c;不少企业都在寻找通过LLM解决企业业务问题的方法&#xff0c;以达到降本增效的效果。但是&#xff0c;当面对较为复杂的业务问题&#xff08;如&#xff1a;背景资料多、问题分类多、条件判断复杂、涉及模块多等&a…

儿童玩具跨境电商/TEMU平台要求北美CPC认证欧洲CE认证

儿童玩具跨境电商/TEMU平台要求北美CPC认证欧洲CE认证 最近Temu严格抽查一份关于儿童用品合规的通知。通知指出&#xff0c;为了保障Temu平台消费者的合法权益&#xff0c;以及保障儿童类商品在目的国的正常销售及合规要求&#xff0c;对于以12岁及以下儿童为主要使用对象的产…

《Webpack 5 基础配置》- 禁止在出现编译错误或警告时,覆盖浏览器全屏显示

Webpack5 overlay 配置地址默认编译错误或警告为 true&#xff0c;即浏览器全屏显示&#xff1b;overlay 属性可以是 boolean 型&#xff0c;也可是 object 类型&#xff1b;还有其它设置说明&#xff0c;详见上述官网地址&#xff1b; module.exports {devServer: {client: {…