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

Leetcode.146 LRU 缓存

题目链接

Leetcode.146 LRU 缓存 mid

题目描述

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类:

  • LRUCache(int capacity)正整数 作为容量 c a p a c i t y capacity capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 k e y key key 存在于缓存中,则返回关键字的值,否则返回 − 1 -1 1
  • void put(int key, int value) 如果关键字 k e y key key 已经存在,则变更其数据值 v a l u e value value ;如果不存在,则向缓存中插入该组 k e y − v a l u e key-value keyvalue 。如果插入操作导致关键字数量超过 c a p a c i t y capacity capacity ,则应该 逐出 最久未使用的关键字。

函数 g e t get get p u t put put 必须以 O ( 1 ) O(1) O(1) 的平均时间复杂度运行。

示例:

输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是
{1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1); // 返回
1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1
作废,缓存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3);
// 返回 3 lRUCache.get(4); // 返回 4

提示:
  • 1 ≤ c a p a c i t y ≤ 3000 1 \leq capacity \leq 3000 1capacity3000
  • 0 ≤ k e y ≤ 10000 0 \leq key \leq 10000 0key10000
  • 0 ≤ v a l u e ≤ 1 0 5 0 \leq value \leq 10^5 0value105
  • 最多调用 2 ∗ 1 0 5 2 * 10^5 2105 g e t get get p u t put put

解法:双向链表 + 哈希表

我们先设计出双向链表的节点 Node

struct Node{Node* prev;Node* next;int key;int val;Node(int k,int v){key = k;val = v;prev = nullptr;next = nullptr;}
};

我们开始设计链表的 API。

struct LinkedList{Node* head; //链表头节点(假)Node* tail; //链表尾节点(假)unordered_map<int,Node*> mp; //根据键值 key 获得对应的节点 nodeint size; //节点数量 , 初始为0int capacity; //链表容量,即链表最多能由几个节点,多了的节点就移除
};    

每次我们通过 g e t get get p u t put put 操作节点之后,我们就要将其移动到链表头部,所以我们需要一个节点 node 插入到链表头部的函数 add

void add(Node* node){head->next->prev = node;node->next = head->next;head->next = node;node->prev = head;
}

此外,我们需要从链表中删除指定节点 node

void remove(Node* node){node->prev->next = node->next;node->next->prev = node->prev;
}

当链表中的节点数量 s i z e size size 超过链表容量 c a p a c i t y capacity capacity 时 ,即 s i z e > c a p a c i t y size > capacity size>capacity。我们就需要移除尾部的节点 并且 从 m p mp mp 删除对应的 k e y key key n o d e node node 的关系:

void remove(){Node* node = tail->prev; //要删除的是尾部的节点remove(node);int key = node->key;mp.erase(key);size--; //移除节点,链表节点数量 - 1
}

对于 g e t get get,如果不存在 k e y key key 对应的节点,直接返回 − 1 -1 1;如果存在 ,返回对应节点 n o d e node node 的值,并且将 n o d e node node 提升到链表头部:

int get(int key){if(!mp.count(key)) return -1;Node* node = mp[key];int ans = node->val;//如果此时 node 已经是第一个节点了,就没必要移动了,直接返回node->valif(node == head->next) return ans;//将 node 移动到链表头部remove(node);add(node);return ans;
}

对于 p u t put put,如果存在 k e y key key 对应的节点,我们更新节点值,然后将节点移动到头部即可;如果不存在,那我们直接插入新的节点 N o d e ( k e y , v a l u e ) Node(key,value) Node(key,value),如果此时超出容量,还要移除尾部的节点:

void put(int key,int value){if(mp.count(key)){Node* node = mp[key];node->val = value;if(node == head->next) return;remove(node);add(node);return;}Node* node = new Node(key,value);mp[key] = node;add(node);size++;if(size > capacity) remove();
}

时间复杂度: O ( 1 ) O(1) O(1)

完整代码:

struct Node{Node* prev;Node* next;int key;int val;Node(int k,int v){key = k;val = v;prev = nullptr;next = nullptr;}
};struct LinkedList{Node* head;Node* tail;unordered_map<int,Node*> mp;int size;int capacity;LinkedList(int c){head = new Node(-1,-1);tail = new Node(-1,-1);head->next = tail;tail->prev = head;size = 0;capacity = c;}void put(int key,int value){if(mp.count(key)){Node* node = mp[key];node->val = value;if(node == head->next) return;remove(node);add(node);return;}Node* node = new Node(key,value);mp[key] = node;add(node);size++;if(size > capacity) remove();}int get(int key){if(!mp.count(key)) return -1;Node* node = mp[key];int ans = node->val;if(node == head->next) return ans;remove(node);add(node);return ans;}void add(Node* node){head->next->prev = node;node->next = head->next;head->next = node;node->prev = head;}void remove(){Node* node = tail->prev;remove(node);int key = node->key;mp.erase(key);size--;}void remove(Node* node){node->prev->next = node->next;node->next->prev = node->prev;}
};class LRUCache {
public:LinkedList* list;LRUCache(int capacity) {list = new LinkedList(capacity);}int get(int key) {return list->get(key);}void put(int key, int value) {list->put(key,value);}
};/*** 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 缓存

题目链接 Leetcode.146 LRU 缓存 mid 题目描述 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类&#xff1a; LRUCache(int capacity) 以 正整数 作为容量 c a p a c i t y capacity capacity 初始化 LRU 缓存int get(int key) 如果关键…...

科技资讯|Canalys发布全球可穿戴腕带设备报告,智能可穿戴增长将持续

市场调查机构 Canalys 近日发布报告&#xff0c;表示 2023 年第 2 季度全球可穿戴腕带设备出货量达 4400 万台&#xff0c;同比增长了 6%。 主要归功于其亲民的价格以及消费者对价位较高的替代品仍持谨慎态度&#xff0c;基础手环市场尽管与去年同期相比有所下降&#xff0c;…...

使用https接口,无法调通接口响应不安全

网页pc使用不安全https 页面提示不安全–点击高级–跳过 接口使用部安全https 无法像页面一样可以跳过 方法&#xff1a;安装证书 还是无法响应报错不安全&#xff1a; 1、确定证书绑定ip还是域名&#xff08;ip和域名都可以绑定&#xff09; 使用的是httpsip&#xff0c;报…...

uniapp开发h5,解决项目启动时,Network: unavailable问题

网上搜了很多&#xff0c;发现都说是要禁用掉电脑多余的网卡&#xff0c;这方法我试了没有好&#xff0c;不晓得为啥子&#xff0c;之后在网上看&#xff0c;uniapp的devServer vue2的话对标的就是webpack4的devserver&#xff08;除了复杂的函数配置项&#xff09;&#xff0c…...

9.17 校招 实习 内推 面经

绿泡*泡&#xff1a; neituijunsir 交流裙 &#xff0c;内推/实习/校招汇总表格 1、自动驾驶一周资讯 - 一汽与Mobileye 签署战略合作&#xff0c;小鹏汽车将用经销商销售逐渐替换直营模式&#xff0c;原小鹏汽车副总裁加盟赛力斯 自动驾驶一周资讯 - 一汽与Mobileye 签署战…...

【Python小项目之Tkinter应用】随机点名/抽奖工具大优化:新增查看历史记录窗口!语音播报功能!修复预览文件按钮等之前版本的bug!

文章目录 前言一、实现思路二、关键代码查看历史记录按钮语音播报按钮三、完整代码总结前言 老生常谈,先看效果:(订阅专栏可获取完整代码) 初始状态下,我们为除了【设置】外的按钮添加弹窗,提示用户在使用工具之前要先【设置】。在设置界面,我们主要修改了【预览文件】…...

数据结构与算法:排序算法(1)

目录 冒泡排序 思想 代码实现 优化 鸡尾酒排序 优缺点 适用场景 快速排序 介绍 流程 基准元素选择 元素交换 1.双边循环法 使用流程 代码实现 2.单边循环法 使用流程 代码实现 3.非递归实现 排序在生活中无处不在&#xff0c;看似简单&#xff0c;背后却隐藏…...

NotePad++ 在行前/行后添加特殊字符内容方法

我们在处理数据时&#xff0c;会遇到需要在每行数据前面、后面、开头、结尾添加各种不一样的字符 如果数据不多&#xff0c;我们可以自己手动的去添加&#xff0c;但如果达到了成百上千行&#xff0c;此时再机械的手动添加是不现实的 这里教给大家如何快速的在数据每行的前后…...

【JavaEE】多线程案例-线程池

文章目录 1. 什么是线程池2. 为什么要使用线程池&#xff08;线程池有什么优点&#xff09;3. 如何使用Java标准库提供的线程池3.1 创建一个线程池对象3.2 什么是工厂模式3.3 为什么要使用工厂模式3.4 Executors 创建不同具有不同特性的线程池3.5 ThreadPool 类的构造方法3.6 线…...

服务器搭建(TCP套接字)-fork版(服务端)

基础版的服务端虽然基本实现了服务器的基本功能&#xff0c;但是如果客户端的并发量比较大的话&#xff0c;服务端的压力和性能就会大打折扣,为了提升服务端的并发性能&#xff0c;可以通过fork子进程的方式&#xff0c;为每一个连接成功的客户端fork一个子进程&#xff0c;这样…...

缺失的第一个正数:高效解法与技术

缺失的第一个正数&#xff1a;高效解法与技术 背景 在计算机编程中&#xff0c;有时候需要寻找一个未排序整数数组中没有出现的最小的正整数。这篇技术博客将详细讨论这个问题&#xff0c;并提供一个时间复杂度为 O(n) 且只使用常数级别额外空间的解决方案。 问题描述 leet…...

常用的辅助网站(持续更新)

标题 一、uni-app方向二、H5方向 一、uni-app方向 1、uni-app官网 地址&#xff1a;https://uniapp.dcloud.net.cn/ 2、香蕉云编 地址&#xff1a;https://www.yunedit.com/ 描述&#xff1a;一般用来配置ios证书或安卓证书、上传ios包至商店 3、uView 地址&#xff1a;http…...

LeetCode 75 - 01 : 最小面积矩形

type pair struct{x, y int }func minAreaRect(points [][]int)int{mp : map[pair]struct{}{}// 将二维数组中的坐标映射到map中for i : range points{mp[pair{points[i][0], points[i][1]}] struct{}{}}// 将结果设置为一个最大值&#xff0c;防止影响求最小值的逻辑res : ma…...

每日一题:请解释什么是闭包(Closure)?并举一个实际的例子来说明。(前端初级)

今天继续在前端初级笔试题中被AI虐&#xff1a; 碱面的答案&#xff0c;问题&#xff1a;初级&#xff0c;回答&#xff1a;初级https://bs.rongapi.cn/1702510598371151872/14我的回答如下&#xff1a; 闭包是指由大括号包裹的一个区域&#xff0c;这个区域代表了一个变量生效…...

广告主必看!NetMarvel五大优势驱动出海App投放增长

App出海走到今天&#xff0c;流量红利早就不存在&#xff0c;摆在广告主面前最棘手的两个问题&#xff0c;一是不起量&#xff0c;二是买量成本太高&#xff0c;得不偿失。 如何在确保出海应用用户规模有所增长的同时&#xff0c;也保证整体ROI处在较高水平&#xff1f;NetMar…...

数据结构与算法之复杂度

时间复杂度 1.抓大头 2.常数用o(1),低阶函数也用o(1)代替&#xff08;直接去掉&#xff09; 3.取最坏情况 对数相关写法的规定...

ATECLOUD电源测试软件平台如何测试电源纹波?

电源纹波是影响电源稳定性的重要因素&#xff0c;过大的纹波会导致电源模块的工作效率降低&#xff0c;可能使电源模块直接损坏。使用ATECLOUD碘盐测试软件平台对纹波进行测试&#xff0c;检测其工作情况&#xff0c;以确保其稳定性和性能。 电源纹波的产生 电源的纹波通俗的来…...

数据结构与算法:排序算法(2)

目录 堆排序 使用步骤 代码实现 计数排序 适用范围 过程 代码实现 排序优化 桶排序 工作原理 代码实现 堆排序 二叉堆的特性&#xff1a; 1. 最大堆的堆顶是整个堆中的最大元素 2. 最小堆的堆顶是整个堆中的最小元素 以最大堆为例&#xff0c;如果删除一个最大堆的…...

1_图神经网络GNN基础知识学习

文章目录 安装PyTorch Geometric安装工具包 在KarateClub数据集上使用图卷积网络 (GCN) 进行节点分类两个画图函数Graph Neural Networks数据集&#xff1a;Zacharys karate club network.PyTorch Geometric数据集介绍 edge_index使用networkx可视化展示 Graph Neural Networks…...

瑞芯微:基于RK3568的ocr识别

光学字符识别&#xff08;Optical Character Recognition, OCR&#xff09;是指对文本资料的图像文件进行分析识别处理&#xff0c;获取文字及版面信息的过程。亦即将图像中的文字进行识别&#xff0c;并以文本的形式返回。OCR的应用场景 卡片证件识别类&#xff1a;大陆、港澳…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

掌握 HTTP 请求:理解 cURL GET 语法

cURL 是一个强大的命令行工具&#xff0c;用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中&#xff0c;cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...

0x-3-Oracle 23 ai-sqlcl 25.1 集成安装-配置和优化

是不是受够了安装了oracle database之后sqlplus的简陋&#xff0c;无法删除无法上下翻页的苦恼。 可以安装readline和rlwrap插件的话&#xff0c;配置.bahs_profile后也能解决上下翻页这些&#xff0c;但是很多生产环境无法安装rpm包。 oracle提供了sqlcl免费许可&#xff0c…...

ubuntu22.04 安装docker 和docker-compose

首先你要确保没有docker环境或者使用命令删掉docker sudo apt-get remove docker docker-engine docker.io containerd runc安装docker 更新软件环境 sudo apt update sudo apt upgrade下载docker依赖和GPG 密钥 # 依赖 apt-get install ca-certificates curl gnupg lsb-rel…...

【若依】框架项目部署笔记

参考【SpringBoot】【Vue】项目部署_no main manifest attribute, in springboot-0.0.1-sn-CSDN博客 多一个redis安装 准备工作&#xff1a; 压缩包下载&#xff1a;http://download.redis.io/releases 1. 上传压缩包&#xff0c;并进入压缩包所在目录&#xff0c;解压到目标…...