腾讯一面-LRU缓存

为了设计一个满足LRU(最近最少使用)缓存约束的数据结构,我们可以使用哈希表(HashMap)来存储键值对,以便在O(1)时间复杂度内访问任意键。同时,我们还需要一个双向链表(Doubly Linked List)来保持键的使用顺序,以便在O(1)时间复杂度内执行插入和删除操作。
我们使用了一个ListNode类来表示双向链表中的节点,每个节点包含键、值、指向前一个节点的指针和指向后一个节点的指针。LRUCache类包含了容量、哈希表、双向链表的头节点和尾节点。
get方法首先检查键是否存在于哈希表中。如果存在,则将对应的节点移到双向链表的头部,并返回节点的值。如果不存在,则返回-1。
put方法首先检查键是否存在于哈希表中。如果不存在,则创建一个新的节点,将其添加到哈希表和双向链表的头部,并检查是否超出了容量。如果超出了容量,则删除双向链表尾部的节点,并从哈希表中移除对应的键值对。如果键已经存在,则更新节点的值,并将其移到双向链表的头部。
addToHead、removeNode、moveToHead和removeTail是辅助方法,用于在双向链表中添加节点、删除节点、将节点移到头部和删除尾部节点。
代码如下:
import java.util.HashMap;
import java.util.Map;class ListNode {int key;int value;ListNode prev;ListNode next;ListNode(int k, int v) {key = k;value = v;}
}class LRUCache {private int capacity;private Map<Integer, ListNode> map;private ListNode head;private ListNode tail;public LRUCache(int capacity) {this.capacity = capacity;map = new HashMap<>();head = new ListNode(0, 0);tail = new ListNode(0, 0);head.next = tail;tail.prev = head;}public int get(int key) {ListNode node = map.get(key);if (node == null) {return -1;}moveToHead(node);return node.value;}public void put(int key, int value) {ListNode node = map.get(key);if (node == null) {// 如果 key 不存在,创建一个新的节点ListNode newNode = new ListNode(key, value);// 添加进哈希表map.put(key, newNode);// 添加进双向链表头部addToHead(newNode);// 如果超出容量,删除双向链表尾部节点if (map.size() > capacity) {ListNode tail = removeTail();map.remove(tail.key);}} else {// 如果 key 存在,先通过哈希表定位,再修改 value,并移到头部node.value = value;moveToHead(node);}}private void addToHead(ListNode node) {node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;}private void removeNode(ListNode node) {node.prev.next = node.next;node.next.prev = node.prev;}private void moveToHead(ListNode node) {removeNode(node);addToHead(node);}private ListNode removeTail() {ListNode res = tail.prev;removeNode(res);return res;}
}
addToHead(ListNode node)
这个方法用于将一个新的节点添加到双向链表的头部。
-
设置新节点的
prev指针:新节点的prev指针指向当前的头节点(head)。 -
设置新节点的
next指针:新节点的next指针指向头节点的下一个节点(head.next)。 -
更新头节点下一个节点的
prev指针:因为新节点被插入到了头节点和头节点的下一个节点之间,所以需要更新头节点的下一个节点的prev指针,使其指向新节点。 -
更新头节点的
next指针:最后,更新头节点的next指针,使其指向新节点,这样新节点就成为了双向链表的新头节点。
removeNode(ListNode node)
这个方法用于从双向链表中移除一个节点。
-
更新被移除节点前一个节点的
next指针:将被移除节点的prev指针所指向的节点的next指针更新为被移除节点的next指针,这样前一个节点就“跳过”了被移除的节点。 -
更新被移除节点后一个节点的
prev指针:将被移除节点的next指针所指向的节点的prev指针更新为被移除节点的prev指针,这样后一个节点也“跳过”了被移除的节点。
moveToHead(ListNode node)
这个方法用于将一个已存在的节点从双向链表的当前位置移动到头部。
-
调用
removeNode方法:首先,使用removeNode方法将被移动的节点从双向链表中移除。 -
调用
addToHead方法:然后,使用addToHead方法将被移除的节点(现在是游离的)添加到双向链表的头部。
removeTail()
这个方法用于移除双向链表的尾部节点,并返回该节点。
-
获取尾部节点的前一个节点:由于尾节点(
tail)的prev指针指向了双向链表的最后一个实际存储数据的节点,所以tail.prev就是我们要移除的尾部节点。 -
调用
removeNode方法:使用removeNode方法移除尾部节点。 -
返回被移除的节点:返回被移除的尾部节点。
注意:在removeTail方法中,实际上并没有直接更新tail指针,因为按照LRU缓存的逻辑,尾部节点在移除后通常不需要再被引用。然而,如果出于某种原因需要保持tail指针的有效性(比如在某些实现中,你可能想要保持一个有效的尾部引用以便快速添加新节点到尾部),你可能需要在移除尾部节点后更新tail指针,使其指向新的尾部节点(即原尾部节点的前一个节点)。但在你提供的代码中,这个步骤是省略的,因为tail节点始终是一个哑节点(dummy node),不存储实际数据。
相关文章:
腾讯一面-LRU缓存
为了设计一个满足LRU(最近最少使用)缓存约束的数据结构,我们可以使用哈希表(HashMap)来存储键值对,以便在O(1)时间复杂度内访问任意键。同时,我们还需要一个双向链表(Doubly Linked …...
k8s实战-1
k8s实战-1 一、资源创建方式1.命令行2.yaml 二、命名空间三、Pod总结 一、资源创建方式 1.命令行 就是直接通过命令的方式创建,比如我要创建namespace, kubectl create namespace hello删除: kubectl delete -f hello2.yaml 简单来说&am…...
Python进程池:提升你的并发性能
引言 在现代编程中,多核处理器的普及使得并发编程变得尤为重要。Python,作为一种广泛使用的编程语言,提供了多种并发和并行编程的工具。其中,multiprocessing库中的进程池(Pool)是一个强大的工具ÿ…...
内存占用估算方法
优质博文:IT-BLOG-CN 通过掌握每种数据类型的大小,就可以更准确地预测对象和数据的内存消耗。 一、基础数据类型 Java基础数据类型结构,在64位系统开启指针压缩情况下的内存占用字节数: booleanbytecharshortintlongfloatdoub…...
拓扑排序简介
拓扑排序(Topological Sort)是一种重要的图算法,用于对有向无环图(DAG, Directed Acyclic Graph)中的节点进行排序。拓扑排序的结果是一种线性序列,使得对于图中的任意一条有向边(u, v),顶点u都在顶点v之前。这种排序常用于任务调度、编译器依赖关系分析等领域。 拓…...
使用iTextPDF库时,设置文字为中文格式
在使用iTextPDF库时,设置文字为中文格式主要涉及选择合适的中文字体,并确保该字体能够正确渲染中文字符。由于iTextPDF的内置字体通常不支持中文,因此你需要加载一个支持中文的字体文件(如TrueType字体,.ttf文件&#…...
Windows环境下使用Docker配置MySQL数据库
用Docker配置数据库,无论是做开发,还是做生产部署,都非常的方便 它不需要单独安装数据库,也不用担心出现各种环境的配置问题。 本文将分享用Docker配置数据库的步骤,这里用MySQL举例。 其他的数据库如MSSQL…...
快速上手C语言【上】(非常详细!!!)
目录 1. 基本数据类型 2. 变量 2.1 定义格式 和 命名规范 2.2 格式化输入和输出(scanf 和 printf) 编辑 2.3 作用域和生命周期 3. 常量 4. 字符串转义字符注释 5. 操作符 5.1 双目操作符 5.1.1 算数操作符 5.1.2 移位操作符 5.1.3 位操作符…...
[深度学习][python]yolov11+deepsort+pyqt5实现目标追踪
【算法介绍】 YOLOv11、DeepSORT和PyQt5的组合为实现高效目标追踪提供了一个强大的解决方案。 YOLOv11是YOLO系列的最新版本,它在保持高检测速度的同时,通过改进网络结构、优化损失函数等方式,提高了检测精度,能够同时处理多个尺…...
【CSDN入门级教程】
这里写自定义目录标题 欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants 创建一个自定义列表如何创建一个…...
二叉搜索树 (BST) 节点插入、查找、删除、获取最大值、最小值和中序遍历排序等功能
二叉搜索树 (BST) 实现总结 本程序实现了一个简单的二叉搜索树 (BST),支持节点插入、查找、删除、获取最大值、最小值和中序遍历排序等功能。以下是各部分的详细说明。 数据结构 节点定义 struct BinTreeNode {int data; // 节点存储的数…...
unity ps 2d animation 蛇的制作
一、PS的使用 1.打开PS 利用钢笔工具从下往上勾勒填充 2.复制图层,Ctrl T,w调为-100% 3.对齐图层并继续用钢笔工具进行三角勾勒 3.画眼睛,按U快捷键打开椭圆工具,按住Shift可以画圆,填充并复制图层对称。 4.画笔工具,打开小…...
39 C 语言枚举类型、枚举常量、枚举变量、枚举的遍历、枚举数组、枚举与 switch
目录 1 什么是枚举 2 定义枚举类型 2.1 语法格式 2.2 枚举元素的特点 2.3 案例演示 3 枚举变量 3.1 什么是枚举变量 3.2 定义枚举变量的多种方式 3.3 案例演示 1:标准版枚举类型 3.4 案例演示 2:简化版枚举类型 3.5 案例演示 3:匿…...
LabVIEW程序怎么解决 Bug?
在LabVIEW开发过程中,发现和解决程序中的Bug是确保系统稳定运行的关键环节。由于LabVIEW采用图形化编程方式,Bug的排查和处理与传统编程语言略有不同。以下是解决LabVIEW程序中Bug的常见方法和技巧,涵盖从问题发现到解决的多个步骤和角度&…...
AR智能眼镜之战:Meta vs Snap
随着增强现实(AR)技术的发展,各大科技公司都在争夺下一代计算平台的领先地位。Meta(前身为Facebook)和Snap作为其中的两个重要玩家,正在竞相开发能够提供沉浸式体验的AR智能眼镜。在这篇文章中,我们将深入探讨这两家公司可能采用的显示技术和用户体验,并分析它们各自的…...
Spring Boot 集成 Flowable UI 实现请假流程 Demo
博客主页: 南来_北往 系列专栏:Spring Boot实战 在现代企业应用中,工作流管理是一个至关重要的部分。通过使用Spring Boot和Flowable,可以方便地构建和管理工作流。本文将详细介绍如何在Spring Boot项目中集成Flowable UI,…...
毕业设计选题:基于ssm+vue+uniapp的医院管理系统小程序
开发语言:Java框架:ssmuniappJDK版本:JDK1.8服务器:tomcat7数据库:mysql 5.7(一定要5.7版本)数据库工具:Navicat11开发软件:eclipse/myeclipse/ideaMaven包:M…...
自动驾驶系列—线控悬架技术:自动驾驶背后的动力学掌控者
🌟🌟 欢迎来到我的技术小筑,一个专为技术探索者打造的交流空间。在这里,我们不仅分享代码的智慧,还探讨技术的深度与广度。无论您是资深开发者还是技术新手,这里都有一片属于您的天空。让我们在知识的海洋中…...
CTF刷题buuctf
[WUSTCTF2020]颜值成绩查询 拿到相关题目,其实根据功能和参数分析。需要传入一个学号然后进行针对于对应的学号进行一个查询,很可能就会存在sql注入。 其实这道题最难的点,在于过滤了空格,因此我们使用 /**/来过滤空格的限制。…...
Qt QWidget控件
目录 一、概述 二、Qwidget常用属性及函数介绍 2.1 enable 2.2 geometry 2.3 windowTitle 2.4 windowIcon 2.5 cursor 2.6 font 设置字体样式 2.7 toolTip 2.8 focusPolicy焦点策略 2.9 styleSheet 一、概述 widget翻译而来就是小控件,小部件。…...
循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
在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 …...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
Java数值运算常见陷阱与规避方法
整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...
C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...
