【难点】【LRU】146.LRU缓存
题目
法1:基于Java的LinkedHashMap
必须掌握法1。参考链接
关于LinkedHashMap的介绍
class LRUCache {int cap;LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();public LRUCache(int capacity) { this.cap = capacity;}public int get(int key) {if (!cache.containsKey(key)) {return -1;}// 将 key 变为最近使用makeRecently(key);return cache.get(key);}public void put(int key, int val) {if (cache.containsKey(key)) {// 修改 key 的值cache.put(key, val);// 将 key 变为最近使用makeRecently(key);return;}if (cache.size() >= this.cap) {// 链表头部就是最久未使用的 keyint oldestKey = cache.keySet().iterator().next();cache.remove(oldestKey);}// 将新的 key 添加链表尾部cache.put(key, val);}private void makeRecently(int key) {int val = cache.get(key);// 删除 key,重新插入到队尾cache.remove(key);cache.put(key, val);}
}
法2:自定义数据结构
参考链接
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】146.LRU缓存
题目 法1:基于Java的LinkedHashMap 必须掌握法1。参考链接 关于LinkedHashMap的介绍 class LRUCache {int cap;LinkedHashMap<Integer, Integer> cache new LinkedHashMap<>();public LRUCache(int capacity) { this.cap capacity;}public int get…...
基于YOLOv8深度学习的吸烟/抽烟行为检测系统【python源码+Pyqt5界面+数据集+训练代码】目标检测、深度学习实战
《博主简介》 小伙伴们好,我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源,可关注公-仲-hao:【阿旭算法与机器学习】,共同学习交流~ 👍感谢小伙伴们点赞、关注! 《------往期经典推…...
菜鸟学习日记(python)——匿名函数
Python 使用 lambda 来创建匿名函数。 lambda 函数是一种小型、匿名的内联函数,它可以具有任意数量的参数,但只能有一个表达式。 匿名函数的一般格式如下: lambda 参数列表:表达式 表达式用于计算并返回函数结果 lambda 函数通常用于编写…...
CompleteFuture与Future的比较
CompleteFuture的介绍CompleteFuture的特点CompleteFuture的应用场景CompletableFuture的优缺点Future的介绍Future的特点Future的应用场景Future的优缺点CompletableFuture和Future的区别CompletableFuture和Future的关联关系CompletableFuture和Future的使用示例CompletableF…...
数据分享 I 全国市级商品房屋销售数据,shp/excel格式,2005-2020年数据
基本信息. 数据名称: 全国市级商品房屋销售数据 数据格式: Shp、excel 数据时间: 2005-2020年 数据几何类型: 面 数据坐标系: WGS84坐标系 数据来源:网络公开数据 数据字段: 序号字段名称字段说明1spxse商品房销售额(亿元…...
面试题总结(十一)【C++】【华清远见西安中心】
C和C的区别有哪些? C 和 C 是两种不同的编程语言,它们有以下一些区别: 1. 语言起源和发展:C 语言是由贝尔实验室的 Dennis Ritchie 在 1972 年开发的,主要用于系统编程和底层开发;而 C 语言是在 C 语言的基…...
c++_01_名字空间_复合类型_缺省参数_哑元函数
0 前言 C和C一样,都属于编译型语言 C和C一样,都属于强类型语言 C对C完全兼容,并提供更多面向对象的特性:语言风格更加简洁,类型检查更加严格 1 名字空间 namespace WHY?划分更精细的逻辑单元(逻辑空间)&…...
前端常见面试题之html和css篇
文章目录 一、html1. 如何理解html语义化2. 说说块级元素和内联元素的区别 二、css1. 盒模型的宽度offsetWidth如何计算2. box-sizing:border-box有什么用3. margin的纵向重叠问题4. 谈谈你对BFC的理解和应用5. 清除浮动有哪些方式6. 使用flex布局实现骰子37.position的absolut…...
使用libaom处理av1编码教程
使用libaom处理av1编码教程 文章目录 使用libaom处理av1编码教程一. av1 是什么二. av1 用处三. libaom 是什么四. libaom 安装五. libaom 安装完成六. 解码av1 一. av1 是什么 AV1(AOMedia Video 1)是一种 开源视频编码格式 。它由开放媒体联盟 (AOM) …...
面试题总结(十)【数据库】【华清远见西安中心】
数据库的分类有哪些? 数据库可以按照不同的标准进行分类,以下是一些常见的数据库分类方式: 1. 关系型数据库(Relational Database):关系型数据库采用表格的形式来组织数据,数据之间通过键值关联…...
计算机网络:物理层(三种数据交换方式)
今天又学到一个知识,加油! 目录 前言 一、电路交换 二、报文交换 三、分组交换 1、数据报方式 2、虚电路方式 3、比较 总结 前言 为什么要进行数据交换? 一、电路交换 电路交换原理:在数据传输期间,源结点与…...
ubuntu18.04 64 位安装笔记——备赛笔记——2024全国职业院校技能大赛“大数据应用开发”赛项——任务2:离线数据处理
进入VirtuakBox官网,网址链接:Oracle VM VirtualBoxhttps://www.virtualbox.org/ 网页连接:Ubuntu Virtual Machine Images for VirtualBox and VMwarehttps://www.osboxes.org/ubuntu/ 将下发的ds_db01.sql数据库文件放置mysql中 12、编写S…...
Nvidia 驱动安装不完整记录
Nvidia 驱动安装不完整记录 安装 epel, sudo dnf install -y https://dl.fedoraproject.org/pub/epel/epel-releaselatest-8.noarch.rpm安装 gcc-toolset-11-gcc, dnf install gcc-toolset-11-gcc修改 gcc,make,as 为 gcc-tools…...
龙芯loongarch64服务器编译安装gcc-8.3.0
前言 当前电脑的gcc版本为8.3.0,但是在编译其他依赖包的时候,出现各种奇怪的问题,会莫名其妙的中断编译。本地文章讲解如何自编译安装gcc,替换系统自带的gcc。 环境准备 下载页面:龙芯开源社区网站 - LoongArch GCC 8.3 交叉工具链 - 源码下载源码包名称如:loongson-gnu…...
宏基因组学Metagenome-磷循环Pcycle功能基因分析-从分析过程到代码及结果演示-超详细保姆级流程
大背景介绍 生信分析,凡事先看论文,有了论文就有了参考,后续分析就有底了,直接上硬菜开干: PCycDB: a comprehensive and accurate database for fast analysis of phosphorus cycling genes - PubMed 数据库及部分分析代码github库: GitHub - ZengJiaxiong/Phospho…...
element plus 日期范围 自定义内容
问题: 按照官网上的自定义内容示例,修改日期选择器没有问题,如果修改日期范围选择器,修改后会丢失日期范围选择时的样式。 解决: 从F12中不难看出日期范围的选择样式来自于.el-date-table-cell 而示例中写的是.cell&…...
[23] GaussianAvatars: Photorealistic Head Avatars with Rigged 3D Gaussians
[paper | proj] 给定FLAME,基于每个三角面片中心初始化一个3D Gaussian(3DGS);当FLAME mesh被驱动时,3DGS根据它的父亲三角面片,做平移、旋转和缩放变化;3DGS可以视作mesh上的辐射场࿱…...
JSON Ajax
1. JSON概念 JSON,全称JavaScript Object Notation,即JavaScript对象表示法,是一种轻量级的数据交换格式。它基于JavaScript的子集,易于人阅读和编写,同时也易于机器解析和生成。 JSON的诞生,是为了解决电…...
ElasticSearch与HBase的分布式存储设计
本文内容覆盖如今两大非结构化数据库之间的区别 详情介绍 从各个角度详细对比 1. 官方定位 HBase 是 Hadoop 数据库,是一个分布式、可扩展的大数据存储。 当您需要对大数据进行随机、实时的读/写访问时,请使用 Apache HBase™。 这个项目的目标是在商用硬件集群上托管非常大…...
回归预测 | MATLAB实现NGO-SCN北方苍鹰算法优化随机配置网络的数据回归预测 (多指标,多图)
回归预测 | MATLAB实现NGO-SCN北方苍鹰算法优化随机配置网络的数据回归预测 (多指标,多图) 目录 回归预测 | MATLAB实现NGO-SCN北方苍鹰算法优化随机配置网络的数据回归预测 (多指标,多图)效果一览基本介绍…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.
ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #:…...
HTML前端开发:JavaScript 获取元素方法详解
作为前端开发者,高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法,分为两大系列: 一、getElementBy... 系列 传统方法,直接通过 DOM 接口访问,返回动态集合(元素变化会实时更新)。…...
