当前位置: 首页 > 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;大陆、港澳…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...