LeetCode 面试题 16.25. LRU 缓存
文章目录
- 一、题目
- 二、C# 题解
一、题目
设计和构建一个“最近最少使用”缓存,该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值),并在初始化时指定最大容量。当缓存被填满时,它应该删除最近最少使用的项目。
它应该支持以下操作: 获取数据 get 和 写入数据 put。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。
示例:
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
点击此处跳转题目。
二、C# 题解
LRU 的思想就是将不常使用的元素优先级设置最低。因此算法规则如下:
- 新数据插入到链表头部;
- 当缓存命中(即缓存数据被访问),数据要移到表头;
- 当链表满的时候,将链表尾部的数据丢弃。
这里使用数组存储链表结构,因为简单高效。
public class LRUCache {private struct Node{public int Key, Value, Left, Right;}private int _cap, _size;private Node[] _list; // 带头结点的双向链表数组实现,_list[0] 作为头结点private int FirstPos { // 第一个结点的物理位置存储在 _list[0].Right 中get => _list[0].Right;set => _list[0].Right = value;}private int RearPos { // 尾结点的物理位置存储在 _list[0].Left 中get => _list[0].Left;set => _list[0].Left = value;}private Dictionary<int, int> _dic;public LRUCache(int capacity) {_cap = capacity;_size = 0;_list = new Node[_cap + 1]; // _list[0] 用作 head 结点,存储 first 和 rear 位置_dic = new Dictionary<int, int>(); // 记录 key 所在结点的位置 pos}public int Get(int key) {// Cache 中存在 key,则将其移到表头,并返回对应的 valueif (_dic.TryGetValue(key, out int pos)) {MoveToFirst(pos);return _list[pos].Value;}// 不存在,返回 -1return -1;}public void Put(int key, int value) {// Cache 中存在 key,则将其移到表头,并更新 valueif (_dic.TryGetValue(key, out int pos)) {MoveToFirst(pos);_list[pos].Value = value;}// 不存在 keyelse {// 链表未满,则直接插入新结点if (_size < _cap) {AddNode(key, value, ++_size); // 新结点的物理位置在数组的下一个位置_dic.Add(key, _size); // 添加 key 的记录}// 链表已满,需要移除尾结点,将新结点插入表头else {int rear = RearPos; // 记录此时的尾结点位置ReMoveAt(rear); // 移除尾结点_dic.Remove(_list[rear].Key);AddNode(key, value, rear); // 向表头插入新结点,物理位置就存储在刚删掉的尾结点 rear 处_dic.Add(key, rear);}}}// 向表头插入结点,结点存储在 _list[pos] 的位置中private void AddNode(int key, int value, int pos) {// 创建结点_list[pos].Key = key;_list[pos].Value = value;// 插入表头_list[pos].Left = 0;_list[pos].Right = FirstPos;_list[FirstPos].Left = pos;FirstPos = pos;}// 将 pos 位置处的结点移到表头private void MoveToFirst(int pos) {ReMoveAt(pos); // 将该结点从链表中移出AddNode(_list[pos].Key, _list[pos].Value, pos); // 再插入表头}// 将 _list[pos] 处的结点从链表中移除private void ReMoveAt(int pos) {int leftPos = _list[pos].Left;int rightPos = _list[pos].Right;_list[leftPos].Right = rightPos;_list[rightPos].Left = leftPos;}
}/*** 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);*/
- 时间:176 ms,击败 100.00% 使用 C# 的用户
- 内存:64.35 MB,击败 85.71% 使用 C# 的用户
相关文章:
LeetCode 面试题 16.25. LRU 缓存
文章目录 一、题目二、C# 题解 一、题目 设计和构建一个“最近最少使用”缓存,该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值),并在初始化时指定最大容量。当缓存被填满时,它应该删除最近最少使用的…...
LaTeX 数学公式常见问题及解决方案
本文汇总了博主在使用 LaTeX 写文档过程中遇到的所有数学公式常见问题及对应的 LaTeX 解决方案 持续更新... 目录 1. 连等式2. 公式重新开始编号2.1 图片/表格重新编号 1. 连等式 在数学公式推导过程中常常会遇到如 Figure 1 所示的连等式,一般需要保证等号或者不等…...
2023最新软件测试20个基础面试题及答案
什么是软件测试? 答案:软件测试是指在预定的环境中运行程序,为了发现软件存在的错误、缺陷以及其他不符合要求的行为的过程。 软件测试的目的是什么? 答案:软件测试的主要目的是保证软件的质量,并尽可能大…...
JMeter-BeanShell预处理程序和BeanShell后置处理程序的应用
一、什么是BeanShell? BeanShell是用Java写成的,一个小型的、免费的、可以下载的、嵌入式的Java源代码解释器,JMeter性能测试工具也充分接纳了BeanShell解释器,封装成了可配置的BeanShell前置和后置处理器,分别是 BeanShell Pre…...
Java声明式事务实战!工作中用这几种就够了!
文章目录 1.几种常用的事务传播行为1.1 REQUIRED1.2 REQUIRES_NEW1.2 NESTED 2. 事务问题2.1 事务不生效?2.2 事务不回滚? 文章会分为两个部分来讲解,第一部分是声明式事务的几种使用场景。第二部分包含事务没有生效,没有回滚的情…...
Abp6.0 使用 appsettings.json配置Serilog.Sinks.MariaDB
Abp6.0中已经启用Serilog,使用Serilog.Sinks.MariaDB包可以保存到MariaDB,mysql中 一种做法是在var loggerConfiguration new LoggerConfiguration( )后使用WriteTo.MariaDB扩展方法来配置,这样在代码中配置不够灵活,修改起来也不方便 其实…...
关于Flume-Kafka-Flume的模式进行数据采集操作
测试是否连接成功: 在主节点flume目录下输入命令: bin/flume-ng agent -n a1 -c conf/ -f job/file_to_kafka.conf -Dflume.root.loggerinfo,console # 这个file_to_kafka.conf文件就是我们的配置文件 然后在另一台节点输入命令进行消费数据: kafka-cons…...
WeTab--颜值与实力并存的浏览器插件
一.前言 现在的浏览器花花绿绿,有大量的广告与信息,令人目不暇接。有没有一款好用的浏览器插件可以解决这个问题呢?我愿称WeTab为版本答案。 WeTab的界面: 干净又整洁。最最关键的是还有智能AI供你服务。 这个WeTabAI就像chatgp…...
【整理】HTTP相关版本对比
1. HTTP/1 超文本传输协议,处于计算机网络中的应用层,HTTP是建立在TCP协议之上,所以HTTP协议的瓶颈及其优化技巧都是基于TCP协议本身的特性。 缺陷: 连接无法复用 ---------- 每次请求经历三次握手和慢启动HOLB(队头…...
spark性能调优 | 默认并行度
Spark Sql默认并行度 看官网,默认并行度200 https://spark.apache.org/docs/2.4.5/sql-performance-tuning.html#other-configuration-options 优化 在数仓中 task最好是cpu的两倍或者3倍(最好是倍数,不要使基数) 拓展 在本地 task需要自己设置&a…...
Python-pptx教程之二操作已有PPT模板文件
文章目录 简单的案例找到要修改的元素修改幻灯片中的文本代码使用示例 修改幻灯片的图片代码使用示例 删除幻灯片代码使用示例 获取PPT中所有的文本内容获取PPT中所有的图片总结 在上一篇中我们已经学会了如何从零开始生成PPT文件,从零开始生成较为复杂的PPT是非常消…...
生活总是自己的,请尽情打扮,尽情可爱,,
同色系拼接羽绒服了解一下 穿上时尚感一下子就突显出来了 90白鸭绒填充,不仅时尚还保暖 设计感满满的羽绒服不考虑一下吗?...
栈和队列的初始化,插入,删除,销毁。
目录 题外话 顺序表和链表优缺点以及特点 一.栈的特点 二. 栈的操作 2.1初始化 2.2 栈的销毁 2.3 栈的插入 2.3 输出top 2.4 栈的删除 2.5 输出栈 题外话 顺序表和链表优缺点以及特点 特点:顺序表,逻辑地址物理地址。可以任意访问,…...
重温《Unix设计哲学》
重温Unix设计哲学 这个世界是复杂的,但往往本质的东西都是简单的。这些原则,不光是用在程序开发,也适用于架构设计,产品设计等等地方。 简洁原则:以简洁为美 不要为了满足自己的虚荣心,企图搞一些花哨的东…...
AIGC创作系统ChatGPT源码,AI绘画源码,支持最新GPT-4-Turbo模型,支持DALL-E3文生图
一、AI创作系统 SparkAi创作系统是基于OpenAI很火的ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统,支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美,可以说SparkAi是目前国内一款的ChatGPT对接OpenAI软件系统。那么如…...
Spring条件注解@Conditoinal+ Profile环境切换应用@Profile
Spring条件注解 一、创建一个maven项目 <dependencies><dependency><groupId>org.springframework</groupId><artifactId>spring-context</artifactId><version>5.1.5.RELEASE</version></dependency> </dependenc…...
Scrum框架中的Sprint
上图就是sprint里要做的事。Sprint是scrum框架的核心,是所有的想法、主意转换为价值的地方。所有实现产品目标的必要工作都在sprint里完成,这些工作主要包括Sprint 计划(Sprint planning)、每日站会(Daily Scrum&#…...
openfeign、nacos获取接口提供方真实IP
源码分析 client 是 LoadBalancerFeignClient org.springframework.cloud.openfeign.ribbon.LoadBalancerFeignClient#execute public Response execute(Request request, Request.Options options) throws IOException {try {URI asUri URI.create(request.url());String c…...
Linux系统编程学习 NO.9——git、gdb
前言 本篇文章简单介绍了Linux操作系统中两个实用的开发工具git版本控制器和gdb调试器。 git 什么是git? git是一款开源的分布式版本控制软件。它不仅具有网络功能,还是服务端与客户端一体的软件。它可以高效的处理程序项目中的版本管理。它是Linux内…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...
学校招生小程序源码介绍
基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码,专为学校招生场景量身打造,功能实用且操作便捷。 从技术架构来看,ThinkPHP提供稳定可靠的后台服务,FastAdmin加速开发流程,UniApp则保障小程序在多端有良好的兼…...
MMaDA: Multimodal Large Diffusion Language Models
CODE : https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA,它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构…...
ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
