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内…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
Python Ovito统计金刚石结构数量
大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...
Redis:现代应用开发的高效内存数据存储利器
一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...
认识CMake并使用CMake构建自己的第一个项目
1.CMake的作用和优势 跨平台支持:CMake支持多种操作系统和编译器,使用同一份构建配置可以在不同的环境中使用 简化配置:通过CMakeLists.txt文件,用户可以定义项目结构、依赖项、编译选项等,无需手动编写复杂的构建脚本…...
