【LeetCode】【算法】146. LRU缓存

LeetCode - 146.LRU缓存

题目描述

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类:
LRUCache(int capacity)以正整数作为容量capacity初始化 LRU 缓存
int get(int key)如果关键字key存在于缓存中,则返回关键字的值,否则返回 -1 。
void put(int key, int value)如果关键字key已经存在,则变更其数据值value;如果不存在,则向缓存中插入该组key-value 。如果插入操作导致关键字数量超过capacity,则应该逐出最久未使用的关键字。
函数get和put必须以 O(1) 的平均时间复杂度运行。

实现思路

LRU本质就是通过一个队列实现的,对于put函数和get函数,最特别的地方在于访问时需要将访问的节点挪到队尾。

  1. 创建ListNode以实现节点。其中包含int key, int value, ListNode next, ListNode prev(双向指针的实现)
  2. 在LRU类中的属性包括:
    I. 虚拟头尾节点ListNode dummyHead, dummyTail;
    II. HashMap用于以O(1)平均复杂度访问到目标节点Map<Integer, ListNode> map;(如果需要遍历整个链表来找目标节点,就不是O(1)的复杂度了)
    III. int capacity表示链表的容量,这是题目需要指定的
    IV. int listLen用于记录当前链表的长度
  3. 初始化LRU类,就是对上面的这些属性做一个初始化,记得虚拟头尾节点的next属性和prev属性需要相连
  4. put方法思路:
    I. 使用map来检查这个节点是否在链表中;
    ① 如果在链表中,则通过map得到这个节点,将该节点从链表中删除,并给改节点赋予新的值;
    ② 如果不在链表中,又分为listLen>=capacitylistLen<capacity的情况(也就是链表容量是否超过指定容量了)
    情况1:链表当前容量已经达到了指定容量,需要删除最久未访问节点(队头),使用虚拟头结点dummyHead来做删除;根据给定的key和value新建一个节点
    情况2:链表当前容量未达到指定容量,则链表长度++,根据给定的key和value新建一个节点
    II. 利用dummyTail将该节点放到链表的最后,并更新map中的内容
  5. get方法思路:
    I. 使用map来检查这个节点是否在链表中,不在返回-1;
    II. 否则利用map来拿到这个节点,将它从链表中移除;并利用dummyTail将该节点放到链表最后,返回该节点的值

实现代码

class LRUCache {class ListNode{int key;int value;ListNode next;ListNode prev;public ListNode() {}public ListNode(int key, int value) {this.key = key;this.value = value;}}ListNode dummyHead;ListNode dummyTail;Map<Integer, ListNode> map;int capacity;int listLen;public LRUCache(int capacity) {map = new HashMap<>();dummyHead = new ListNode();dummyTail = new ListNode();dummyHead.next = dummyTail;dummyTail.prev = dummyHead;this.capacity = capacity;this.listLen = 0;}public void put(int key, int value) {ListNode listNode = null;// 如果map里面没有这个keyif (!map.containsKey(key)){// 如果长度已经满了,就移除一个if (listLen >= capacity){ListNode removeNode = dummyHead.next;removeNode.next.prev = removeNode.prev;removeNode.prev.next = removeNode.next;map.remove(removeNode.key);} else {listLen++;}// 新增一个listNode = new ListNode(key, value);}// 如果map里有这个keyelse {listNode = map.get(key);// 把这个listNode从链表上删除ListNode prev_node = listNode.prev;ListNode next_node = listNode.next;prev_node.next = next_node;next_node.prev = prev_node;listNode.value = value;}// 把这个listNode弄到后面去ListNode insertPre = dummyTail.prev;insertPre.next = listNode;listNode.prev = insertPre;listNode.next = dummyTail;dummyTail.prev = listNode;map.put(key, listNode);}public int get(int key) {if (!map.containsKey(key)){return -1;} else {int result = map.get(key).value;// 拿到这个Node,移除它ListNode listNode = map.get(key);// 把这个listNode从链表上删除ListNode prev_node = listNode.prev;ListNode next_node = listNode.next;prev_node.next = next_node;next_node.prev = prev_node;// 把这个listNode弄到后面去ListNode insertPre = dummyTail.prev;insertPre.next = listNode;listNode.prev = insertPre;listNode.next = dummyTail;dummyTail.prev = listNode;map.put(key, listNode);return result;}}
}/*** 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.xdnf.cn/news/9204.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

window 利用Putty免密登录远程服务器

1 在本地电脑用putty-gen生成密钥 参考1 参考2 2 服务器端操作 将公钥上传至Linux服务器。 复制上述公钥到服务器端的authorized_keys文件 mkdir ~/.ssh vi ~/.ssh/authorized_keys在vi编辑器中&#xff0c;按下ShiftInsert键或者右键选择粘贴&#xff0c;即可将剪贴板中的文…

【大数据技术基础 | 实验八】HBase实验:新建HBase表

文章目录 一、实验目的二、实验要求三、实验原理四、实验环境五、实验内容和步骤&#xff08;一&#xff09;启动HBase集群&#xff08;二&#xff09;编写项目java代码&#xff08;三&#xff09;将代码导出jar包 六、实验结果七、实验心得 一、实验目的 掌握HBase数据模型(逻…

密钥管理服务 (KMS) 故障排除指南

企业客户将密钥管理服务 (KMS) 设置为部署流程的一部分&#xff0c;因为通过该服务&#xff0c;他们可以使用简单、直接的过程在其环境中激活 Windows。 通常&#xff0c;一旦设置了 KMS 主机&#xff0c;KMS 客户端就会自动连接到主机并自行激活。 然而&#xff0c;有时该流程…

CSS的配色

目录 1 十六进制2 CSS中的十六进制2.1 十六进制颜色的基本结构2.2 十六进制颜色的范围2.3 简写形式2.4 透明度 3 CSS的命名颜色4 配色4.1 色轮4.2 互补色4.3 类似色4.4 配色工具 日常在开发小程序中&#xff0c;客户总是希望你的配色是美的&#xff0c;但是美如何定义&#xff…

基于 RNN 的语言模型

基于 RNN 的语言模型 循环神经网络&#xff08;Recurrent Neural Network, RNN&#xff09;是一类网络连接中包含环路的 神经网络的总称。 给定一个序列&#xff0c;RNN 的环路用于将历史状态叠加到当前状态上。沿着时间维度&#xff0c;历史状态被循环累积&#xff0c;并作为…

【软考网工笔记】网络基础理论——物理层

文章目录 贝尔系统 T1 载波光纤 - SFP接口差分&&曼彻斯特编码网桥MAC-in-MACQ-in-QIPv6的链路本地地址CRC校验与计算E1载波编码效率对称xDSL坚持算法-CSMAUDP头部字段万兆以太网标准 IEEE 802.3ae海明码-纠错码ARP帧中的目标MAC地址快速以太区网物理层标准 100BASE-TXM…

现代Web开发:TypeScript 深入解析与最佳实践

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 现代Web开发&#xff1a;TypeScript 深入解析与最佳实践 现代Web开发&#xff1a;TypeScript 深入解析与最佳实践 现代Web开发&a…

HCIP MPLS基础

一、 实验拓扑 二、 实验需求及解法 本实验模拟BGP路由黑洞环境&#xff0c;使用MPLS LDP解决路由黑洞。 完成以下需求&#xff1a; 1.设备IP地址配置&#xff0c;请测试直连。 sysname R1 interface GigabitEthernet0/0/0ip address 12.1.1.1 255.255.255.0interface Loop…

Kubernetes架构及核心组件

一、基本架构 Kubernetes集群可以被看作是一个工厂,而各个组件则是这个工厂里的不同部门: Kubernetes API服务器:就像是这个工厂的总经理,负责接收所有的请求并将它们分配给相应的部门进行处理。 etcd:就像是这个工厂的记事本,负责记录所有的配置信息和状态信息,以便其…

移动开发(七):.NET MAUI使用RESTAPI实现查询天气笔记

目录 一、接口准备 二、实体部分 三、页面部分 四、后台代码逻辑 五、总结 在移动开发过程中,第三方对接是非常常见的。今天给大家分享.NET MAUI如何使用REST API实现输入城市名称查询天气的示例,希望对大家学习.NET MAUI可以提供一些帮助! 一、接口准备 首先我们需要…

聊聊基于BERT模型实现多标签分类任务的实践与思考

概述 以预训练大模型为基座神经网络模型&#xff0c;通过模型预训练后的泛化能力与微调后的领域能力&#xff0c;作为NLP任务的解决方案。 在github上找了一个简单的仓库——multi_label_classification&#xff0c;该仓库基于BERT预训练大模型实现了多分类任务。通过对该仓库…

C语言 【大白话讲指针(中)】

在之前的文章中我们已经知道了指针的概念&#xff0c;指针就是一个变量&#xff0c;用来存放地址&#xff0c;地址指向唯一一块内存空间。指针的大小是固定的4/8个字节&#xff08;32为机器/64位机器&#xff09;。指针是有类型的&#xff0c;指针的类型决定了指针加减整数的步…

大数据分析在市场营销中的应用

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 大数据分析在市场营销中的应用 大数据分析在市场营销中的应用 大数据分析在市场营销中的应用 引言 大数据分析概述 定义与原理 发…

启明云端触觉智能与您相约2024年慕尼黑国际电子元器件博览会,不见不散!

展会信息 展会日期: 2024年11月12-15日 展馆名称: 慕尼黑国际展览中心 MesseMnchen exhibition center 展馆地址: Messegelnde 81829 Mnchen Germany 启明云端&触觉智能展位号&#xff1a;B6-351 诚邀您莅临我司展位&#xff0c;让我们在慕尼黑不见不散&#xff01; …

OPPO开源Diffusion多语言适配器—— MultilingualSD3-adapter 和 ChineseFLUX.1-adapter

MultilingualSD3-adapter 是为 SD3 量身定制的多语言适配器。 它源自 ECCV 2024 的一篇题为 PEA-Diffusion 的论文。ChineseFLUX.1-adapter是为Flux.1系列机型量身定制的多语言适配器&#xff0c;理论上继承了ByT5&#xff0c;可支持100多种语言&#xff0c;但在中文方面做了额…

【JavaEE初阶】网络原理(4)

欢迎关注个人主页&#xff1a;逸狼 创造不易&#xff0c;可以点点赞吗~ 如有错误&#xff0c;欢迎指出~ 目录 网络层 > IP协议 IP协议报头结构 4位版本 4位首部长度 8位服务类型(TOS) 16位总长度(字节数), 16位标识 3位标志位 13位片偏移 8位生存时间(TTL) 8位协议 16位首部…

树莓派上安装与配置 Nginx Web 服务器教程

在树莓派上配置 Nginx 作为 Web 服务器的步骤如下&#xff1a; 1. 更新树莓派 首先&#xff0c;确保你的树莓派系统是最新的。打开终端并执行以下命令&#xff1a; sudo apt update sudo apt upgrade -y2. 安装 Nginx 在树莓派上安装 Nginx&#xff1a; sudo apt install …

Android Studio 中关于com.github.barteksc:android-pdf-viewer 无法正确加载的问题

Android Studio 的app 模块下&#xff0c;添加依赖&#xff1a; implementation com.github.barteksc:android-pdf-viewer:3.2.0-beta.1 运行程序报错&#xff1a; Caused by: org.gradle.api.internal.artifacts.ivyservice.DefaultLenientConfiguration$ArtifactResolveEx…

[JAVA]Maven项目标准结构介绍

什么是Maven&#xff1f; Maven 是一个强大的项目管理和构建自动化工具&#xff0c;在Java开发中&#xff0c;一个项目通常会依赖许多外部的库&#xff0c;比如开发一个Web应用可能需要依赖Servlet APL&#xff0c;Spring框架等&#xff0c;和需要引入大量的Jar包。往往一个Ja…

Ansys EMC Plus:MHARNESS 串扰演示

Ansys EMC Plus 是一款强大的工具&#xff0c;专门用于分析电磁场及其影响&#xff0c;涵盖电磁兼容性和雷电效应分析等领域。 在本演示中&#xff0c;我们将探讨建立 MHARNESS 仿真的基础知识。这包括构建基本电缆线束、创建 MHARNESS 源和设置 MHARNESS 探针的过程。 概述 …