【模拟-BM100 设计LRU缓存结构】

题目

BM100 设计LRU缓存结构

描述
设计LRU(最近最少使用)缓存结构,该结构在构造时确定大小,假设大小为 capacity ,操作次数是 n ,并有如下功能:

  1. Solution(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  2. get(key):如果关键字 key 存在于缓存中,则返回key对应的value值,否则返回 -1 。
  3. set(key, value):将记录(key, value)插入该结构,如果关键字 key 已经存在,则变更其数据值 value,如果不存在,则向缓存中插入该组 key-value ,如果key-value的数量超过capacity,弹出最久未使用的key-value

提示:
1.某个key的set或get操作一旦发生,则认为这个key的记录成了最常使用的,然后都会刷新缓存。
2.当缓存的大小超过capacity时,移除最不经常使用的记录。
3.返回的value都以字符串形式表达,如果是set,则会输出"null"来表示(不需要用户返回,系统会自动输出),方便观察
4.函数set和get必须以O(1)的方式运行
5.为了方便区分缓存里key与value,下面说明的缓存里key用""号包裹

在这里插入图片描述

在这里插入图片描述

分析

python 的话,直接用collection 中的 OrderedDict

OrderedDict 是 Python 标准库 collections 模块中的一个特殊字典类,其核心特性是维护了元素添加的顺序。这与 Python 3.7 及以上版本中的普通字典不同,尽管普通字典现在也保持插入顺序,但 OrderedDict 提供了一些额外的功能,这些功能在普通字典中不可用。

顺序性:
OrderedDict 记录了元素被添加到字典中的顺序。这对于需要元素顺序的场景(如实现LRU缓存)非常有用。

重排功能:
使用 move_to_end 方法可以将一个键值对移动到有序字典的末尾或开头,这在调整元素顺序时非常方便。

常用方法
popitem(last=True): 弹出并返回一个键值对。如果 last 为 True(默认值),则按 LIFO(后进先出)顺序返回最后一个添加的元素;如果为 False,则按 FIFO(先进先出)顺序返回第一个添加的元素。
move_to_end(key, last=True): 将存在的键 key 移动到字典的末尾(如果 last=True)或字典的开头(如果 last=False)。
示例代码
下面是一个简单的示例,展示了 OrderedDict 的一些基本用法:

from collections import OrderedDict# 创建有序字典
od = OrderedDict()
od['a'] = 1
od['b'] = 2
od['c'] = 3# 访问顺序
for key, value in od.items():print(key, value)  # a 1, b 2, c 3# 移动元素 'b' 到末尾
od.move_to_end('b')
for key, value in od.items():print(key, value)  # a 1, c 3, b 2# 弹出最先加入的元素
od.popitem(last=False)
for key, value in od.items():print(key, value)  # c 3, b 2

代码

from collections import OrderedDictclass Solution:def __init__(self, capacity: int):# write code hereself.capacity = capacityself.lru_cache = OrderedDict()def get(self, key: int) -> int:# write code hereif key in self.lru_cache:self.lru_cache.move_to_end(key)return self.lru_cache.get(key,-1)def set(self, key: int, value: int) -> None:# write code hereif key in self.lru_cache:# self.lur_cache.move_to_end(key)del self.lru_cache[key]self.lru_cache[key] = valueif len(self.lru_cache)>self.capacity:self.lru_cache.popitem(last=False)# Your Solution object will be instantiated and called as such:
# solution = Solution(capacity)
# output = solution.get(key)
# solution.set(key,value)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/347362.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

windows音频服务未响应,电脑装完驱动还是软件导致没有声音

前两天浏览器突然没声音了,然后我试着搞了一下驱动,结果全没声音了。 至今仍然不确定问题的根源在哪,并且网上提供的大部分方法都没用,下面说一下我的解决方案。 winR启动命令行,输入services.msc 进入服务界面 双击…

OpenCV 双目相机标定

文章目录 一、简介1.1单目相机标定1.2双目相机标定二、实现代码三、实现效果参考资料一、简介 1.1单目相机标定 与单目相机标定类似,双目标定的目的也是要找到从世界坐标转换为图像坐标所用到的投影P矩阵各个系数(即相机的内参与外参)。具体过程如下所述: 1、首先我们需要…

r语言数据分析案例26-美元兑换欧元汇率分析与研究

一、研究背景: 汇率是国际贸易和金融中最重要的价格之一,它直接影响着各国的经济利益和国际竞争力。美元兑换欧元汇率是全球最重要的汇率之一,它的波动对全球经济和金融市场都有着深远的影响。因此,对美元兑换欧元汇率的分析和研…

MySQL学习——创建MySQL Workbench中的Connections

在MySQL Workbench中,Connections(连接)是用户与MySQL数据库进行交互的桥梁。 本文将添加一个新连接,该连接可以是初始连接,也可以是附加连接。在开始之前,必须安装、启动MySQL服务器的实例,并…

什么是SpringMVC

StringMvc简介 Spring web mvc和Struts2都属于表现层的框架,它是Spring框架的一部分,我们可以从Spring的整体结构中看得出来:

DevExpress Data Binding

DevExpress数据感知控件与任何数据访问技术(ADO.NET、Entity Framework、XPO等)兼容,并且可以显示来自实现IList、IBindingList或ITypedList接口的任何数据源的数据。有关更多详细信息,请参阅这些帮助主题:传统数据绑定…

python中用列表实现栈

【小白从小学Python、C、Java】 【考研初试复试毕业设计】 【Python基础AI数据分析】 python中用列表实现栈 选择题 以下代码最后一次输出的结果是? stack [] stack.append(1) stack.append(2) stack.append(3) print(【显示】stack ,stack) print(【显示】stack.…

【python】OpenCV—Background Estimation(15)

文章目录 中值滤波中值滤波得到图像背景移动侦测 学习来自 OpenCV基础(14)OpenCV在视频中的简单背景估计 中值滤波 中值滤波是一种非线性平滑技术,主要用于数字信号处理,特别是在图像处理中去除噪声。 一、定义与原理 定义&am…

面试官:MySQL也可以实现分布式锁吗?

首先说结论,可以做,但不推荐做。 我们并不推荐使用数据库实现分布式锁。 如果非要这么做,实现大概有两种。 1、锁住Java的方法,借助insert实现 如何用数据库实现分布式锁呢,简单来说就是创建一张锁表,比…

JVM 根可达算法

Java中的垃圾 Java中"垃圾"通常指的是不再被程序使用和引用的对象,具体表现在没有被栈、JNI指针和永久代对象所引用的对象。Java作为一种面向对象的编程语言,它使用自动内存管理机制,其中垃圾收集器负责检测和回收不再被程序引用的…

集成学习概述

概述 集成学习(Ensemble learning)就是将多个机器学习模型组合起来,共同工作以达到优化算法的目的。具体来讲,集成学习可以通过多个学习器相结合,来获得比单一学习器更优越的泛化性能。集成学习的一般步骤为:1.生产一组“个体学习…

开源WebGIS全流程常用技术栈

1 数据生产 1.1 uDig uDig(http://udig.refractions.net/)是一个基于Java开源的桌面应用框架,它构建在Eclipse RCP和GeoTools(一个开源的Java GIS包)上。可以进行shp格式地图文件的编辑和查看;是一个开源空间数据查看…

excel两个数据表格,怎样实现筛选的联动?

如图,想要通过处理器或者像素条件进行筛选,形成一个右边图2的对比表,如何实现实现联动显示呢? 这个在excel里可以借用数据透视表切片器来完成。步骤如下: 1.添加表 选中数据区域中任意一个单元格,点击 插…

跳动圆点加载动画

效果图: 完整代码: <!DOCTYPE html> <html> <head><meta charset="UTF-8" /><title>跳动圆点加载动画</title><style type="text/css">body {background: #ECF0F1;display: flex;justify-content: center;al…

“改进型”Howland 电流泵电路

“改进型”Howland 电流泵电路 “改进型”Howland 电流泵是一种使用差分放大器在分流电阻器 (Rs) 上施加电压的电路&#xff0c;从而产生能够驱动大范 围负载电阻的双极性&#xff08;拉电流或灌电流&#xff09;压控电流源。 设计注释 确保运算放大器的输入端&#xff08;V…

串口调试助手软件(ATK-XCOM) 版本:v2.0

串口设置 软件启动后&#xff0c;会自动搜索可用的串口&#xff0c;可以显示详细的串口信息&#xff0c;由于兼容性原因某些电脑可能不会显示。 超高波特率接收&#xff0c;在硬件设别支持的情况下&#xff0c;可自定义波特率&#xff0c;点“自定义”即可输入您想要的波特率&…

pycharm爬取BOSS直聘岗位信息

编译器&#xff1a;Pycharm 效果展示如图 简单原理描述&#xff1a;模拟人工动作爬取页面信息&#xff0c;运行脚本后代码自动打开浏览器获取相关信息&#xff0c;模拟人工进行页面跳转并自动抓取页面信息记录到表格中。 深入原理描述&#xff1a;页面翻转的时候会调用接口&am…

用人工智能写2024年高考作文

目录 用人工智能写2024年高考作文 引用 一、2024年 新课标I卷 作文真题 AI写作范文 二、2024年 全国甲卷 作文真题 AI写作范文 三、2024年 新课标II卷 作文真题 AI写作范文 四、2024年 北京卷 作文真题一 AI写作范文 作文真题二 AI写作范文 作文真题三 AI写作…

MySQL是怎么保证持久性的(redo log日志相关)

Mysql中 事务的很多实现&#xff0c;都是因为有日志的支撑&#xff0c;比如binlog、undo log、redo log等 MySQL是怎么保证持久性的 持久性是指&#xff0c;事务一旦提交&#xff0c;它对数据库的改变就应该是永久性的&#xff0c;接下来的其他操作或故障不能对其有影响。In…

Linux/Windows 安装 RocketMQ 详细图文教程!

Linux 安装 RocketMQ 首先&#xff0c;你需要从RocketMQ的官方网站或GitHub仓库下载最新的RocketMQ发行版下载安装&#xff0c;官网下载地址&#xff1a;https://rocketmq.apache.org/download/。 接下来配置环境变量&#xff1a; 输入vim /etc/profile命令配置环境变量输入i进…