【leetcode hot 100 146】LRU缓存

解法一:(哈希表 + 双向链表)LRU 缓存机制可以通过哈希表辅以双向链表实现,我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。

  • 双向链表按照被使用的顺序存储了这些键值对,靠近头部的键值对是最近使用的,而靠近尾部的键值对是最久未使用的。
  • 哈希表即为普通的哈希映射(HashMap),通过缓存数据的键映射到其在双向链表中的位置。
class LRUCache {class DLinkNode{int key;int value;DLinkNode prev;DLinkNode next;// 记得写构造函数public DLinkNode(){}public DLinkNode(int key, int value){this.key=key; this.value=value;}}private Map<Integer,DLinkNode> mapID = new HashMap<>();private int capacity;private int size;private DLinkNode head,tail;  // 全部放到构造函数去初始化public LRUCache(int capacity) {this.capacity = capacity;this.size = 0;head = new DLinkNode();tail = new DLinkNode();head.next = tail;tail.prev = head;}public int get(int key) {DLinkNode node = mapID.get(key);if(node==null){return -1;}// 将node放到双链表头部,表示刚刚访问过moveToHead(node);return node.value;}public void put(int key, int value) {DLinkNode node = mapID.get(key);if(node==null){// 不存在:申请node,放在头部,超过数量就删除尾部DLinkNode newNode = new DLinkNode(key, value);addNode(newNode);mapID.put(key,newNode); // mapID也要做相应的put和removesize++;if(size>capacity){DLinkNode tail = deleteTail();// mapID.remove(key)不可,要返回删除的key,以此为准来一移除mapID.remove(tail.key);size--;}}else{// 已经存在:修改v值,移到最前面node.value = value;moveToHead(node);}}private void moveToHead(DLinkNode node){removeNode(node);addNode(node);}private DLinkNode removeNode(DLinkNode node){node.prev.next = node.next;node.next.prev = node.prev;return node;}private void addNode(DLinkNode node){node.next = head.next;head.next = node;node.prev = head;node.next.prev = node;}private DLinkNode deleteTail(){DLinkNode res = removeNode(tail.prev);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);*/

注意:

  • 参数的初始化全部放到构造函数去初始化
  • 双链表进行添加和移除时候,mapID也要做相应的putremove
  • mapID进行移除时,mapID.remove(key)不可,要返回删除的key,以此为准来一移除
  • 双链表DLinkNode用于维护最近使用策略,哈希表mapID用于提供getset操作

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

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

相关文章

深度学习中的向量的样子-DCN

深度学习中向量都是 竖着的&#xff0c;譬如 DCN中的计算逻辑

OBS推WebRTC流,并添加毫秒级时间显示

作者在用OBS推WebRTC流&#xff0c;并用浏览器观看推送的实时流。另外就是想看一下延迟有多少。采用一台电脑&#xff0c;流媒体服务器为SRS&#xff0c;相关配置比较简单&#xff0c;可以自行搜索。 推送的流 http://localhost:1985/rtc/v1/whip/?applive&streamlivestr…

【MySQL】多表操作 —— 外键约束

目录 多表关系一对一关系一对多/多对一关系多对多关系 外键约束基本概念一对多/多对一创建外键约束外键约束下的数据操作数据插入数据删除 删除外键约束 多对多创建外键约束外键约束下的数据操作数据插入数据删除 删除外键约束 多表关系 MySQL 多表之间的关系可以概括为&#…

82.HarmonyOS NEXT 性能优化指南:从理论到实践

温馨提示&#xff1a;本篇博客的详细代码已发布到 git : https://gitcode.com/nutpi/HarmonyosNext 可以下载运行哦&#xff01; HarmonyOS NEXT 性能优化指南&#xff1a;从理论到实践 文章目录 HarmonyOS NEXT 性能优化指南&#xff1a;从理论到实践1. 性能优化概述1.1 性能指…

树莓派急速安装ubuntu;映射磁盘与储存磁盘文件;ubuntu映射整个工程;保存系统工作状态

一、用途 在使用树莓派上下载ubuntu时&#xff0c;需要一张sd卡&#xff0c;当你需要给这张卡做备份的时候&#xff0c;可以是使用磁盘映射软件&#xff0c;从而达到备份的目的 同时有一些大佬发布了ubuntu的映射文件&#xff0c;可以直接使用该文件&#xff0c;然后还原他的整…

Qt 控件概述 QPushButton 与 QRadioButton

目录 QPushButton setIcon 设置图标 setShortCut 设置快捷键 setAutoRepeat : 设置是否连发 ​编辑RadioButton 槽函数 单选按钮的分组排异 QPushButton QPushButtoon继承于QAbstractButton(抽象类)&#xff1b; QAbstract中与QPushButton关联性极大的属性 ​ setIcon…

HR9110 玩具单通道直流电机驱动器

1、描述 HR9110是应用于直流电机方案的单通道H桥驱动器芯片。HR9110的H桥驱动部分采用低导通电阻的PMOS和NMOS功率管。低导通电阻保证芯片低的功率损耗&#xff0c;使得芯片安全工作更长时间。此 外HR9110拥有低待机电流、低静态工作电流。这些性能使能HR9110易用于玩具方案。…

Mac 使用 Crossover 加载 Windows Steam 游戏库,实现 Windows/Mac 共享移动硬盘

Mac 使用 Crossover 加载 Windows Steam 游戏库&#xff0c;实现 Windows/Mac 共享移动硬盘 1. 在Crossover上安装Steam2. Steam容器加载移动硬盘3. 配置Steam库 前言&#xff1a;本文介绍了如何在Crossover上安装Steam并加载外接移动硬盘&#xff0c;实现在Window上下载的游戏…

ubuntu 24 安装 python3.x 教程

目录 注意事项 一、安装不同 Python 版本 1. 安装依赖 2. 下载 Python 源码 3. 解压并编译安装 二、管理多个 Python 版本 1. 查看已安装的 Python 版本 2. 配置环境变量 3. 使用 update-alternatives​ 管理 Python 版本 三、使用虚拟环境为项目指定特定 Python 版本…

沐数科技数据开发岗笔试题2025

描述性统计 标准差 答案: A 解析: 标准差 衡量数据集中数值变化或离散程度的一种度量。它反映了数据集中的各个数值与数据集的平均值&#xff08;均值&#xff09;之间的偏离程度。标准差越大&#xff0c;表明数据的分布越分散&#xff1b;标准差越小&#xff0c;表明数据…

ChatGPT-4

第一章&#xff1a;ChatGPT-4的技术背景与核心架构 1.1 生成式AI的发展脉络 生成式人工智能&#xff08;Generative AI&#xff09;的演进历程可追溯至20世纪50年代的早期自然语言处理研究。从基于规则的ELIZA系统到统计语言模型&#xff0c;再到深度学习的革命性突破&#x…

vulkanscenegraph显示倾斜模型(5.3)-相机

前言 在Vulkan中&#xff0c;相机的概念并非由API直接提供&#xff0c;而是由应用程序实现。相机的核心功能包括视图变换和投影变换&#xff1a;视图变换将世界坐标系中的物体转换到相机坐标系&#xff0c;投影变换则将相机坐标系中的物体转换到投影空间。在VSG&#xff08;Vul…

【Pycharm】Pycharm无法复制粘贴,提示系统剪贴板不可用

我也没有用vim的插件&#xff0c;检查了本地和ubutnu上都没有。区别是我是远程到ubutnu的pycharm&#xff0c;我本地直接控制windowes的pycharm是没问题的。现象是可以从外部复制到pycharm反之则不行。 ctl c ctlv 以及右键 都不行 参考&#xff1a;Pycharm无法复制粘贴&…

MySQL 8 设置允许远程连接(Windows环境)

&#x1f31f; MySQL 8 设置允许远程连接&#xff08;Windows环境&#xff09; 在开发和部署应用时&#xff0c;经常需要从远程主机连接到MySQL数据库。默认情况下&#xff0c;MySQL仅允许本地连接&#xff0c;因此需要进行一些配置才能允许远程访问。今天&#xff0c;我将详细…

Prosys OPC UA Gateway:实现 OPC Classic 与 OPC UA 无缝连接

在工业自动化的数字化转型中&#xff0c;设备与系统之间的高效通信至关重要。然而&#xff0c;许多企业仍依赖于基于 COM/DCOM 技术的 OPC 产品&#xff0c;这给与现代化的 OPC UA 架构的集成带来了挑战。 Prosys OPC UA Gateway 正是为解决这一问题而生&#xff0c;它作为一款…

欢乐力扣:基本计算器

文章目录 1、题目描述2、思路代码括号 1、题目描述 基本计算器。  给你一个字符串表达式 s &#xff0c;请你实现一个基本计算器来计算并返回它的值。  注意:不允许使用任何将字符串作为数学表达式计算的内置函数&#xff0c;比如 eval() 。 2、思路 本人也不太会&#xff0c…

SVN学习笔记

svn:版本控制软件 解决&#xff1a;1.协作开发 2.远程开发 3.版本回退 服务端软件&#xff1a; VisualSVN http://www.visualsvn.com 客户端软件:Tortoisesvn http://tortoisesvn.net/downloads 1.checkout(检出) 第一查更新数据到本地&#xff0c; 2.update&#xf…

Mysql表的查询

一&#xff1a;创建一个新的数据库&#xff08;companydb),并查看数据库。 二&#xff1a;使用该数据库&#xff0c;并创建表worker。 mysql> use companydb;mysql> CREATE TABLE worker(-> 部门号 INT(11) NOT NULL,-> 职工号 INT(11) NOT NULL,-> 工作时间 D…

[ISP] 人眼中的颜色

相机是如何记录颜色的&#xff0c;又是如何被显示器还原的&#xff1f; 相机通过记录RGB数值然后显示器显示RGB数值来实现颜色的记录和呈现。道理是这么个道理&#xff0c;但实际上各厂家生产的相机对光的响应各不相同&#xff0c;并且不同厂家显示器对三原色的显示也天差地别&…

Cursor插件市场打不开解决

问题现象&#xff1a; cursor搜索插件的时候提示错误&#xff0c;无法搜索安装插件 error while fetching extensions.failed to fetch 问题原因 cursor默认安装使用的并不是vs code的插件市场&#xff0c;国内网络有时候打不开 解决 修改插件市场地址并重启cursor 打开cur…