当前位置: 首页 > news >正文

LRU cache的实现细节优化——伪结点的技巧

LRU cache的实现是面试常见的题目,思路比较简单,可以参考思路
这个题目在实际面试中容易出错,主要是npe和头节点与尾节点的更新,有没有办法避免这一点呢,这时可以发现伪节点的好处,永远不用更新头尾节点,也不用担心出现npe

在双向链表的实现中,使用一个伪头部(dummy head)和伪尾部(dummy tail)标记界限,这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。

代码实现:

import java.util.HashMap;
import java.util.Map;public class LRUCache {class DLinkedNode {int key;int value;DLinkedNode prev;DLinkedNode next;public DLinkedNode() {}public DLinkedNode(int _key, int _value) {key = _key; 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;}
}

相关文章:

LRU cache的实现细节优化——伪结点的技巧

LRU cache的实现是面试常见的题目&#xff0c;思路比较简单&#xff0c;可以参考思路 这个题目在实际面试中容易出错&#xff0c;主要是npe和头节点与尾节点的更新&#xff0c;有没有办法避免这一点呢&#xff0c;这时可以发现伪节点的好处&#xff0c;永远不用更新头尾节点&am…...

【C/C++】父类指针指向子类对象 | 隐藏

创作不易&#xff0c;本篇文章如果帮助到了你&#xff0c;还请点赞 关注支持一下♡>&#x16966;<)!! 主页专栏有更多知识&#xff0c;如有疑问欢迎大家指正讨论&#xff0c;共同进步&#xff01; &#x1f525;c系列专栏&#xff1a;C/C零基础到精通 &#x1f525; 给大…...

NSSCTF——Web题目2

目录 一、[HNCTF 2022 Week1]2048 二、[HNCTF 2022 Week1]What is Web 三、[LitCTF 2023]1zjs 四、[NCTF 2018]签到题 五、[SWPUCTF 2021 新生赛]gift_F12 一、[HNCTF 2022 Week1]2048 知识点&#xff1a;源代码审计 解题思路&#xff1a; 1、打开控制台&#xff0c;查看…...

从零到富:探索CSGO搬砖项目的无限可能

在如今互联网时代&#xff0c;有一项令人惊叹的项目正悄然兴起&#xff0c;它就是CSGO搬砖项目。作为一个从零开始的家伙&#xff0c;我亲身经历了这个项目的神奇魅力&#xff0c;每天轻松赚取几十上百的收益&#xff0c;无风险&#xff0c;低成本。今天&#xff0c;我将带领大…...

Uniapp中vuex的使用

vuex的学习笔记&#xff0c;很多地方还都不是很懂&#xff0c;先记下来再说&#xff0c;比小程序里自带的store复杂很多&#xff0c;看着头大&#xff0c;而且方法里面很多ES6的内容&#xff0c;头都看到爆炸 一、初始化vuex 新建store.js&#xff0c;挂载到main.js 1、在根…...

SpringBoot案例-配置文件-参数配置化

前言 目前我们已经完成了部门管理和员工管理功能接口的实现&#xff0c;阿里云OSS工具类中&#xff0c;我们会设置4个参数&#xff0c;分别是云服务域名、云服务ID和密码、文件存储的Bucket、就会存在以下问题&#xff1a;参数配置分散以及参数发生变化&#xff0c;就需要对应…...

android系统启动流程之zygote(Native)启动分析

zygote有一部分运行在native,有一部分运行在java层&#xff0c;它是第一个进入java层的进程 zygote在启动时&#xff0c;在init.${ro.zygote}.rc脚本中&#xff0c;里面描述了zygote是如何被启动的&#xff0c; 当init进程解析到zygote.rc文件时&#xff0c;将根据解析出来的命…...

Win10上ffmpeg出现Invalid report file level

在win10上经常使用ffmpeg&#xff0c;但是最近突然ffmpeg用不了&#xff0c;不管ffmpeg还是ffplay&#xff0c;输出始终一句话&#xff1a; Invalid report file level 重新通过scoop装了以后还是同样的错误。 后来发现是一个环境变量设置有问题&#xff0c;FFREPORT。 我在w…...

Vue3 中引入液晶数字字体(通常用于大屏设计)

一、下载 .ttf 字体文件到本地&#xff0c;放在 src 中的 assets 文件下 下载液晶字体 DS-Digital.ttf 二、在 css 文件中引入字体 /* src/assets/fonts/dsfont.css */ font-face {font-family: electronicFont;src: url(./DS-Digital.ttf);font-weight: normal;font-styl…...

从 Future 到 CompletableFuture:简化 Java 中的异步编程

引言 在并发编程中&#xff0c;我们经常需要处理多线程的任务&#xff0c;这些任务往往具有依赖性&#xff0c;异步性&#xff0c;且需要在所有任务完成后获取结果。Java 8 引入了 CompletableFuture 类&#xff0c;它带来了一种新的编程模式&#xff0c;让我们能够以函数式编…...

【ARMv8 SIMD和浮点指令编程】NEON 乘法指令——乘法知多少?

NEON 乘法指令包括向量乘法、向量乘加和向量乘减,还有和饱和相关的指令。总之,乘法指令是必修课,在我们的实际开发中会经常遇到。 1 MUL (by element) 乘(向量,按元素)。该指令将第一个源 SIMD&FP 寄存器中的向量元素乘以第二个源 SIMD&FP 寄存器中的指定值,将…...

Nginx详解 第三部分:Nginx高级配置(附配置实例)

Part 3 一、网页的状态页二、Nginx第三方模块2.1 echo 模块 三、变量3.1 内置变量3.1.1 常用内置变量3.1.2 举个例子 3.2 自定义变量 四、自定义访问日志 (优化)4.1 自定义访问日志的格式4.2 自定义json 格式日志 五、Nginx压缩功能&#xff08;重要&#xff09;六、HTTPS 功能…...

postman访问ruoyi后台接口

打开若依页面&#xff0c;登录进去&#xff0c;F12打开控制台&#xff0c;选一个后台服务&#xff0c;把下图两个节点&#xff0c;补到postman请求header里面即可...

大数据时代的软件开发实践:利用云计算和AI赋能创新

文章目录 云计算的赋能弹性资源管理远程协作与分布式开发持续集成和持续交付成本效益 人工智能的赋能数据驱动的决策自动化智能预测和优化自适应系统 创新的实践方法数据驱动的创新智能化产品开放式创新迭代和反馈 &#x1f388;个人主页&#xff1a;程序员 小侯 &#x1f390;…...

32、启用 HTTP 响应压缩和编程式配置Web应用

★ 启用HTTP压缩 就是前端页面如果改动的比较多&#xff0c;那么响应就会比较慢&#xff0c;可以通过设置HTTP响应压缩来提高响应&#xff0c;如果前端改动少&#xff0c;那么就不需要启动这个响应压缩。 目的&#xff1a;为了提高HTTP响应数据在网络上的传输效率。▲ 设置如…...

DiskCatalogMaker for Mac简单智能快速的磁盘管理工具

DiskCatalogMaker是一款Mac上的磁盘目录管理工具。它可以帮助用户快速创建和管理磁盘目录&#xff0c;方便查找和访问存储在磁盘上的文件和文件夹。它具有快速扫描和索引功能&#xff0c;生成详细的目录列表&#xff0c;支持关键字搜索和自定义标签。 此外&#xff0c;DiskCat…...

C语言练习5(巩固提升)

C语言练习5 选择题 选择题 1&#xff0c;下面代码的结果是&#xff1a;( ) #include <stdio.h> #include <string.h> int main() {char arr[] { b, i, t };printf("%d\n", strlen(arr));return 0; }A.3 B.4 C.随机值 D.5 &#x1f4af;答案解析&#…...

SSM框架的学习与应用(Spring + Spring MVC + MyBatis)-Java EE企业级应用开发学习记录(第三天)动态SQL

动态SQL—SSM框架的学习与应用(Spring Spring MVC MyBatis)-Java EE企业级应用开发学习记录&#xff08;第三天&#xff09;Mybatis的动态SQL操作 昨天我们深入学习了Mybatis的核心对象SqlSessionFactoryBuilder&#xff0c;掌握MyBatis核心配置文件以及元素的使用,也掌握My…...

Kaggle(3):Predict CO2 Emissions in Rwanda

Kaggle&#xff08;3&#xff09;&#xff1a;Predict CO2 Emissions in Rwanda 1. Introduction 在本次竞赛中&#xff0c;我们的任务是预测非洲 497 个不同地点 2022 年的二氧化碳排放量。 在训练数据中&#xff0c;我们有 2019-2021 年的二氧化碳排放量 本笔记本的内容&am…...

【技巧分享】如何获取子窗体选择了多少记录数?一招搞定!

Hi,大家好久不见。 我这个更新速度是不是太慢了呀&#xff0c;因为&#xff0c;最近又又又在忙&#xff0c;请大家谅解啦。 现在更新文章、视频都要花好久去考虑&#xff0c;好不容易有个灵感了&#xff0c;一搜索&#xff0c;结果发现之前都已经分享过了&#xff08;委屈脸&…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器

拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件&#xff1a; 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...

stm32进入Infinite_Loop原因(因为有系统中断函数未自定义实现)

这是系统中断服务程序的默认处理汇编函数&#xff0c;如果我们没有定义实现某个中断函数&#xff0c;那么当stm32产生了该中断时&#xff0c;就会默认跑这里来了&#xff0c;所以我们打开了什么中断&#xff0c;一定要记得实现对应的系统中断函数&#xff0c;否则会进来一直循环…...