LeetCode-146. LRU 缓存【设计 哈希表 链表 双向链表】
LeetCode-146. LRU 缓存【设计 哈希表 链表 双向链表】
- 题目描述:
- 解题思路一:双向链表,函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。一张图:
- 知识点__slots__
- 解题思路二:0
- 解题思路三:0
题目描述:
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类:
- LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
- int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
- void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 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 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put
解题思路一:双向链表,函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。一张图:

class Node:__slots__ = 'prev', 'next', 'key', 'value' # 提高访问属性的速度,并节省内存def __init__(self, key = 0, value = 0):self.key = keyself.value = valueclass LRUCache:def __init__(self, capacity: int):self.capacity = capacityself.dummy = Node() # 哨兵节点self.dummy.prev = self.dummyself.dummy.next = self.dummyself.key_to_node = dict()def get(self, key: int) -> int:node = self.get_node(key)return node.value if node else -1def put(self, key: int, value: int) -> None:node = self.get_node(key)if node: # 有这本书node.value = value # 更新 valuereturn self.key_to_node[key] = node = Node(key, value) # 新书self.push_front(node) # 放在最上面if len(self.key_to_node) > self.capacity: # 书太多了back_node = self.dummy.prevdel self.key_to_node[back_node.key] # 去掉最后一本书self.remove(back_node) # 去掉最后一本书def get_node(self, key: int) -> Optional[Node]:if key not in self.key_to_node: # 没有这本书return Nonenode = self.key_to_node[key] # 有这本书self.remove(node) # 把这本书抽出来self.push_front(node) # 放在最上面return nodedef remove(self, x: Node) -> None: # 删除一个节点(抽出一本书)x.prev.next = x.nextx.next.prev = x.prevdef push_front(self, x: Node) -> None: # 在链表头添加一个节点(把一本书放在最上面)x.prev = self.dummyx.next = self.dummy.nextx.prev.next = xx.next.prev = x# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
时间复杂度:O(1)
空间复杂度:O(min(p,capacity)),其中 p 为 put 的调用次数。
知识点__slots__
slots 是 Python 中用于优化类的属性访问和节省内存的特殊属性。当你定义一个类时,通常每个实例对象都会有一个字典来存储其属性和方法,这种灵活性使得可以在运行时动态地添加、修改和删除属性。然而,对于某些需要高性能和节省内存的场景,这种灵活性可能会显得过于浪费资源。
slots 的作用就是告诉解释器:这个类的实例只能拥有 slots 中指定的属性,而不再使用字典来存储属性。这样做的好处有两个:
-
提高访问速度: 由于属性被限定在预定义的集合中,访问这些属性时不再需要通过字典查找,而是可以直接定位到它们,因此访问速度会更快。
-
节省内存: 没有了动态属性字典,实例对象所需的内存空间会更小。这在需要大量创建实例对象的场景中尤为有用,可以有效地节省内存资源。
使用 slots 时,你需要在类中定义一个 slots 属性,这个属性是一个字符串组成的元组,用于指定类的实例可以拥有的属性名称。例如:
class MyClass:__slots__ = ('attr1', 'attr2')def __init__(self, a, b):self.attr1 = aself.attr2 = b
在这个例子中,MyClass 的实例只能拥有 attr1 和 attr2 这两个属性,而不能拥有其他动态添加的属性。这样就提高了访问速度和节省了内存。
需要注意的是,使用 slots 也有一些限制:
- 不能动态添加新的属性,因为 slots 指定了固定的属性集合。
- 每个实例只能拥有 slots 中指定的属性,而不能拥有其他属性。
- 继承时如果子类定义了 slots,则父类的 slots 不会被继承。
因此,在需要优化属性访问速度和节省内存的情况下,可以考虑使用 slots。
解题思路二:0
时间复杂度:O(n)
空间复杂度:O(n)
解题思路三:0
时间复杂度:O(n)
空间复杂度:O(n)
相关文章:
LeetCode-146. LRU 缓存【设计 哈希表 链表 双向链表】
LeetCode-146. LRU 缓存【设计 哈希表 链表 双向链表】 题目描述:解题思路一:双向链表,函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。一张图:知识点__slots__ 解题思路二:0解题思路三:0 题目描述&am…...
如何在Python中import其他文件的实时值
在A.py中加入变量TEST_A0后,可以通过不同的方式在B.py中调用该变量。下面是对两种方式的介绍: 使用from A import TEST_A调用TEST_A: 这种方式是直接将A.py中的TEST_A变量导入到B.py中,可以直接使用TEST_A变量,而不需…...
NumPy进阶(二)
2. NumPy进阶(二) 2.1 Numpy数组操作 2.1.1 添加元素 numpy.append 函数在数组的末尾添加值。 追加操作会分配整个数组,并把原来的数组复制到新数组中 注意: 插入的维度要保证所有数组的长度是相同的如果没有指定轴,数组会被扁平处理 ndarr…...
计算机专业,不擅长打代码,考研该怎么选择?
考研其实和你的代码能力关系不大 所以在选学校以前可以看看有哪些学校复试是要求上机撸代码的,可能会要求比较严 初试真的不用担心代码问题,我也是基本零编程能力就开始备考考研的... 本人双非科班出身备考408成功上岸,在这里也想给想考40…...
SQL Server的详细使用教程
安装SQL Server 下载SQL Server 安装程序运行安装程序,选择"基本"安装类型在"实例配置"页面,将实例命名为"SQLServerTest"在"服务器配置"页面,选择"NT服务\系统"作为启动账户完成其他设置,然后安装SQL Server 连接SQL Serve…...
挑错罐头=“害猫”!猫咪主食罐到底应该怎么选?
猫咪罐头已经成为众多猫奴们的喂养首选。它富含水分,有助于猫咪保持良好的泌尿系统健康,尤其对于那些不太喜欢饮水的猫咪来说,罐头无疑是补充水分的理想方式。罐头的口感极佳,肉质细腻,能够激发猫咪的食欲,…...
43---SATA电路设计
视频链接 SATA硬件电路设计01_哔哩哔哩_bilibili SATA电路设计 1、硬盘分类 硬盘按照原理可以分为机械硬盘(HDD)、固态硬盘(SSD)以及混合硬盘(SSHD)三类。 1.1、机械硬盘(HDD) …...
think:该写什么样的blog
前言 好久没更新blog,简单写点东西。随着chatgpt为首的大模型兴起,发现周边的很多程序员逐步减少使用google,Stack Overflow等搜索常见的问题,csdn流量估计也会受到不小的影响。chatgpt的下限不低,从简单的语法查询到…...
【APUE】网络socket编程温度采集智能存储与上报项目技术------多路复用
作者简介: 一个平凡而乐于分享的小比特,中南民族大学通信工程专业研究生在读,研究方向无线联邦学习 擅长领域:驱动开发,嵌入式软件开发,BSP开发 作者主页:一个平凡而乐于分享的小比特的个人主页…...
GitHub 仓库 (repository) Pulse - Contributors - Network
GitHub 仓库 [repository] Pulse - Contributors - Network 1. Pulse2. Contributors3. NetworkReferences 1. Pulse 显示该仓库最近的活动信息。该仓库中的软件是无人问津,还是在火热地开发之中,从这里可以一目了然。 2. Contributors 显示对该仓库进…...
C语言题目:阶乘数列求和(函数)
题目描述 输入一个正数x和一个正整数n,求下列算式的值。要求定义两个调用函数:fact(n)计算n的阶乘;mypow(x,n)计算x的n次幂(即xn),两个函数的返回值类型是double。 x - x2/2! x3/3! ... (-1)n-1xn/n! …...
Unity与CocosCreator对比学习二
一、锚点与适配 1.在Creator中 适配通过锚点、位置和Widget达到适配目的;锚点是节点在其父节点坐标系中坐标对其点,其x,y范围在[0, 1]之间; 锚点为(0, 0)时在节点自身的左下角,节点坐标指其左下角在父节点中的坐标;锚…...
01-Git 快速入门
https://learngitbranching.js.org/?localezh_CN在线练习git 1. Git 安装好Git以后, 先检查是否已经绑定了用户名和邮箱 git config --list再检查C:\Users\xxx.ssh 下是否存在 id_rsa.pub , 存在的话复制其内容到 GitHub 的 SSH KEY 中 没有这一步, PUSH操作的时候会报错:…...
Axure RP中的相关概念及高保真原型构建方法
1 Axure RP中概念介绍 对于构建高保真原型来说,需要知道事件(Event)、Case、Action等概念。Axure RP中给出这些概念,是为了方便原型的构建,尤其是高保真原型的构建。 事件(Event)是附着于控件…...
Ruoyi-vue-pro Vue + nginx 二级目录部署到云服务器
http://www.your-server.com/ 这是一级目录,由于项目多,一般会通过二级域名http://oa.your-server.com/或二级目录http://www.your-server.com/oa来发布,本篇记录一下二级目录发布。先看效果 1、router/index.js配置base export default new …...
leetcode2529--正整数和负整数的最大计数
1. 题意 给定有序数组,求其中正整数和负整数的计数最大值。 正整数和负整数的最大计数 2. 题解 2.1 遍历 直接判断 class Solution { public:int maximumCount(vector<int>& nums) {int neg 0;int pos 0;for (int num:nums) {if (!num)continue;i…...
使用YOLOv8训练自己的【目标检测】数据集
文章目录 1.收集数据集1.1 使用开源已标记数据集1.2 爬取网络图像1.3 自己拍摄数据集1.4 使用数据增强生成数据集1.5 使用算法合成图像 2.标注数据集2.1确认标注格式2.2 开始标注 3.划分数据集4.配置训练环境4.1获取代码4.2安装环境 5.训练模型5.1新建一个数据集yaml文件5.2预测…...
rust学习(recursive mutex 实现)
问题: 编写如下代码的时候出现死锁: pub fn test_double_lock() {let t Arc::new(Mutex::new(1));let t1 t.clone();let t2 t.clone();let h std::thread::spawn(move || {println!("hello trace1");let l1 t1.lock().unwrap();println…...
DasViewer可以添加照片到里面吗?点开就可以看照片?
DasViewer主要是三维模型浏览器,二维可以添加矢量和正射影像,航片暂不支持。 DasViewer是由大势智慧自主研发的免费的实景三维模型浏览器,采用多细节层次模型逐步自适应加载技术,让用户在极低的电脑配置下,也能流畅的加载较大规模实景三维模型,提供方便…...
python蓝桥杯选数
文章目录 前言一、题意二、代码1.代码的实现2.读入数据 总结 前言 本题涉及到很多python中的知识点,比如combinations(列表的组合)应用,以及素数的判断 一、题意 已知 n 个整数 x1,x2,…,xn,以及一个整数 k(k&#x…...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...
