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

方法一:哈希表+双向链表
使用一个哈希表和一个双向链表维护所有在缓存中的键值对
- 双向链表按照被使用的顺序存储了这些键值对,靠近头部的键值对是最近使用的,而靠近尾部的键值对是最久使用的
- 哈希表即为普通的哈希映射,通过缓存数据的键映射到其在双向链表中的位置
这样以来,我们首先使用哈希表进行定位,找出缓存项在双向链表中的位置,随后将其移动到双向链表的头部,即可在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);*/
相关文章:
【LeetCode刷题-链表】--146.LRU缓存
146.LRU缓存 方法一:哈希表双向链表 使用一个哈希表和一个双向链表维护所有在缓存中的键值对 双向链表按照被使用的顺序存储了这些键值对,靠近头部的键值对是最近使用的,而靠近尾部的键值对是最久使用的哈希表即为普通的哈希映射࿰…...
mysql 问题解答
01 Mysql有哪些数据类型 MySQL支持多种数据类型,这些类型可以分为几个大的类别:数值类型、日期和时间类型、字符串(字符和字节)类型、空间类型、JSON类型。下面是每种类型的简要说明和用途,以及示例。 数值类型 整型: TINYINT:非常小的整数,如性别标识(0代表女性,1代…...
组件与Props:React中构建可复用UI的基石
目录 组件:构建现代UI的基本单位 Props:组件之间的数据传递 Props的灵活性:构建可配置的组件 组件间的通信:通过回调函数传递数据 总结: 组件:构建现代UI的基本单位 组件是前端开发中的关键概念之一。…...
接口框架第二篇—unittest/pytest 有什么区别
1.用例编写方法 unittest 1)测试文件必须导入unittest包 2)测试类必须继承unittest.TestCase 3)测试类必须有unittest.main()方法 4)测试方法必须要以test_打头 pytest 1)测试文件名要以test_打头,或…...
Window 7 / 10 / 11 .bat .cmd 中文路径不识别解决方案
一般都是编码问题 我们在批处理的第一行加入: chcp 65001 进行转为UTF-8 编码就可以实现中文路径识别...
Linux命令(113)之rev
linux命令之rev 1.rev介绍 linux命令rev是将文件中的每行内容已字符为单位反向输出,即第一个字符最后输出,最后一个字符最先输出 2.rev用法 rev [参数] filename rev参数 参数说明-V显示版本信息-h显示帮助信息 3.实例 3.1.显示rev的版本信息 命令…...
QT+SQLite数据库配置和使用
一、简介 1.1 SQLite(sql)是一款开源轻量级的数据库软件,不需要server,可以集成在其他软件中,非常适合嵌入式系统。Qt5以上版本可以直接使用SQLite(Qt自带驱动)。 二、下载和配置 2.1 SQLite下载…...
若依分离版——配置多数据源(mysql和oracle),实现一个方法操作多个数据源
目录 一、若依平台配置 二、编写oracle数据库访问的各类文件 三. 一个方法操作多个数据源 一、若依平台配置 1、在ruoyi-admin的pom.xml添加依赖 <dependency> <groupId>com.oracle</groupId> <artifactId>ojdbc6</artifactId> <version…...
Seata入门系列【19】分布式事务之CAP、BASE理论
1 CAP理论 CAP是以下三个词语的缩写: Consistency:一致性Availability:可用性Partition tolerance:分区容忍性 CAP理论的基础概念就是在分布式系统中,无法同时满足以上三点。 下面我们以一个简单的分布式系统&…...
界面控件DevExpress WPF Gauge组件 - 轻松实现个性化商业仪表盘
DevExpress WPF Gauge(仪表)控件包含了多种圆形仪表类型、水平和垂直线性仪表、分段和矩阵数字仪表以及状态指示器,同时还具有最终用户交互性的集成支持。 P.S:DevExpress WPF拥有120个控件和库,将帮助您交付满足甚至…...
算法题:870. 优势洗牌
该算法是临时想出来的,Java代码的实现在时间上不占优,之后有时间要优化一下,目前就是给大家提供一下思路。 解题思路:田忌赛马的思想 贪心法。 Step1. 对两个数组进行排序。 Step2. 同时遍历排序后的nums2和nums1,将…...
[架构之路-252/创业之路-83]:目标系统 - 纵向分层 - 企业信息化的呈现形态:常见企业信息化软件系统 - 企业应用信息系统集成
目录 第一章 什么是企业应用信息系统集成What 1.1 简介 1.2 架构 二、为什么需要企业应用信息系统集成Why 三、如何实现企业应用信息系统集成 3.1 步骤 3.2 企业应用集成的层次 3.3 业务流程重组 第一章 什么是企业应用信息系统集成What 1.1 简介 企业应用信息系统集…...
MFC发送http https以及json解析
域名解析成IP char szWeb[128] "www.baidu.com";struct hostent *pHost NULL;pHost gethostbyname(szWeb);//完成主机名到域名的解析char *IP inet_ntoa(*((struct in_addr *)pHost->h_addr));CString ipStr IP;请求三部曲: 1、CInternetSession…...
UE5加载websocket模块为空
今天测试UE 发现工程启动不了,后来看到原来是websocket模块无法加载。 解决的它的方法很简单,这种问题一般会出现在源码版本的引擎或者是停电了,导致UElaunch版本损坏,解决方法是来到源码版本的引擎 这个目录下: D:\…...
学习 Python 数据可视化,如何快速入门?
Python 是一种非常流行的编程语言,具有简单易学、高效、丰富的库和工具等特点。其中,数据可视化是 Python 的一个重要应用领域,可以帮助人们更好地理解和分析数据。本文将介绍如何快速入门 Python 数据可视化,以及常用的可视化工具…...
XUbuntu22.04之simplenote支持的Markdown语法总结(一百九十一)
简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 人生格言: 人生…...
JAVA深化篇_26——Apache commons-io工具包的使用
Apache commons-io工具包的使用 Apache基金会介绍 Apache软件基金会(也就是Apache Software Foundation,简称为ASF),是专门为支持开源软件项目而办的一个非盈利性组织。在它所支持的Apache项目与子项目中,所发行的软…...
centos 7 kafka2.6单机安装及动态认证SASL SCRAM配置
目录 1.kfaka安装篇 1.1 安装jdk 1.2安装kafka 2.安全篇 2.1 kafka安全涉及3部份: 2.2 Kafka权限控制认证方式 2.3 SASL/SCRAM-SHA-256 配置实例 2.3.1 创建用户 2.3.2 创建 JAAS 文件及配置 3.测试 3.1 创建测试用户 3.2 配置JAAS 文件 3.2.1 生产者配…...
TrafficWatch 数据包嗅探器工具
TrafficWatch 是一种数据包嗅探器工具,允许您监视和分析 PCAP 文件中的网络流量。它提供了对各种网络协议的深入了解,并可以帮助进行网络故障排除、安全分析等。 针对 ARP、ICMP、TCP、UDP、DNS、DHCP、HTTP、SNMP、LLMNR 和 NetBIOS 的特定于协议的数据…...
MySQL Binlog实战应用之一
一、前言 开发业务系统尤其是与财务相关的系统,需要记录每一笔变更操作的日志,这一般有两种实现方案。 1、代码中通过AOP实现,提供注解跟踪记录日志,这种方案能够比较清晰地以业务角度记录操作日志,但记录变更前的旧…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
