LeetCode-146. LRU 缓存【设计 哈希表 链表 双向链表】

news/2024/4/19 17:58:25/

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 中指定的属性,而不再使用字典来存储属性。这样做的好处有两个:

  1. 提高访问速度: 由于属性被限定在预定义的集合中,访问这些属性时不再需要通过字典查找,而是可以直接定位到它们,因此访问速度会更快。

  2. 节省内存: 没有了动态属性字典,实例对象所需的内存空间会更小。这在需要大量创建实例对象的场景中尤为有用,可以有效地节省内存资源。

使用 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)


http://www.ppmy.cn/news/1405474.html

相关文章

Maven入门指南:构建与管理Java项目的利器

引言 在Java开发领域&#xff0c;项目构建和管理是一个至关重要的环节。随着项目规模和复杂度的不断增加&#xff0c;有效地管理项目的依赖、构建过程以及部署流程变得尤为关键。在这样的背景下&#xff0c;Apache Maven作为一款优秀的项目管理工具应运而生&#xff0c;成为了…

STC8H8K64U 学习笔记 - 基础代码

STC8H8K64U 学习笔记 - 基础代码 环境说明引脚说明 基础代码电动马达蜂鸣器小蓝灯LED 灯走马灯来回灯流水灯流水逐灭灯相遇灯 独立按键 串口串口接收查询按键反馈 环境说明 该内容仅针对我自己学习的开发板做的笔记&#xff0c;在实际开发中需要针对目标电路板的原理图进行针对…

使用浏览器打开本地的exe程序并传递参数

使用浏览器打开本地的exe程序并传递参数 html文件 其中OpenProgramByBroswer: 为协议名称&#xff0c;名称后面要跟上英文的冒号。 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport&…

【讲解下Gitea】

&#x1f308;个人主页:程序员不想敲代码啊 &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共…

基于Springboot + MySQL + Vue 大学新生宿舍管理系统 (含源码)

目录 &#x1f4da; 前言 &#x1f4d1;摘要 &#x1f4d1;操作流程 &#x1f4da; 系统架构设计 &#x1f4da; 数据库设计 &#x1f4ac; 管理员信息属性 &#x1f4ac; 学生信息实体属性 &#x1f4ac; 宿舍安排信息实体属性 &#x1f4ac; 卫生检查信息实体属性 &…

使用vuepress搭建个人的博客(一):基础构建

前言 vuepress是一个构建静态资源网站的库 地址:VuePress 一般来说,这个框架非常适合构建个人技术博客,你只需要把自己写好的markdown文档准备好,完成对应的配置就可以了 搭建 初始化和引入 创建文件夹press-blog npm初始化 npm init 引入包 npm install -D vuepress…

docker安装rabbitMQ,并且创建账号

# 创建docker容器启动,挂到后台运行 docker run -d --name rabbitmq -p 5672:5672 -p 15672:15672 rabbitmq:3.13-management # 打开防火墙 sudo firewall-cmd --zonepublic --add-port5672/tcp --permanent sudo firewall-cmd --zonepublic --add-port15672/tcp --permanent s…

P2089 烤鸡——Python解答

题目背景 猪猪 Hanke 得到了一只鸡。 题目描述 猪猪 Hanke 特别喜欢吃烤鸡&#xff08;本是同畜牲&#xff0c;相煎何太急&#xff01;&#xff09;Hanke 吃鸡很特别&#xff0c;为什么特别呢&#xff1f;因为他有 1010 种配料&#xff08;芥末、孜然等&#xff09;&#xf…

【电路笔记】-逻辑与门

逻辑与门 文章目录 逻辑与门1、概述2、2 输入晶体管与门3、数字与门类型4、7408 四路 2 输入与门逻辑与门是一种数字逻辑电路,仅当其所有输入均为高电平时,其输出才会变为高电平至逻辑电平 1。 1、概述 数字逻辑与门的输出状态仅在其任何输入处于逻辑电平“0”时再次返回“低…

知识图谱在五大智能领域的应用

知识图谱是一种新型的图数据模型&#xff0c;其核心思想是&#xff1a;通过实体和关系来描述一个数据集&#xff0c;而不是像传统关系数据库那样&#xff0c;将数据存储在不同的数据库中&#xff0c;而是可以让用户对数据进行检索和分析。知识图谱通过三元组&#xff08;实体、…

Linux提权!!!

上一篇文章讲了Windows的提权&#xff0c;那么这篇文章就来讲一下Linux的提权 1.SUID提权 suid权限 作用&#xff1a;让普通用户临时拥有该文件的属主的执行权限&#xff0c;suid权限只能应用在二进制可执行文件&#xff08;命令&#xff09;上&#xff0c;而且suid权限只能设置…

《QT实用小工具·三》偏3D风格的异型窗体

1、概述 源码放在文章末尾 可以在窗体中点击鼠标左键进行图片切换&#xff0c;项目提供了一些图片素材&#xff0c;整体风格偏向于3D类型&#xff0c;也可以根据需求自己放置不同的图片。 下面是demo演示&#xff1a; 项目部分代码如下所示&#xff1a; 头文件部分&#xff…

linux设置Nacos自启动

前提&#xff1a;已经安装好nacos应用 可参考&#xff1a;Nacos单机版安装-CSDN博客 1. 创建nacos.service 1.1 在 /lib/systemd/system 目录底下&#xff0c;新建nacos.service文件 [Unit] Descriptionnacos Afternetwork.target[Service]Typeforking# 单机启动方式&#…

I2C总线与AT24C02

目录 I2C总线 I2C总线介绍 I2C电路规范 I2C时序结构 起始与终止 代码理解 发送字节 代码理解 接收字节 代码理解 数据应答 代码理解 I2C的数据据帧 发送数据帧 接收数据帧 发送接收数据帧 AT24C02芯片 AT24C02介绍 引脚及应用电路 内部结构图 AT24C02数据…

对【AI技术创业】有哪些机会进行分析和引导

文章目录 方向一&#xff1a;行业解决方案,以下是一些常见的行业解决方案&#xff1a;方向二&#xff1a;智能产品和服务,以下是一些智能产品和服务的示例&#xff1a;方向三&#xff1a;教育和培训 1.智能客户服务&#xff1a; 利用自然语言处理&#xff08;NLP&#xff09;和…

【Algorithms 4】算法(第4版)学习笔记 23 - 5.4 正则表达式

文章目录 前言参考目录学习笔记1&#xff1a;正则表达式1.1&#xff1a;表示1.2&#xff1a;快捷表示2&#xff1a;正则表达式与非确定有限状态自动机 REs and NFAs2.1&#xff1a;二元性2.2&#xff1a;模式匹配实现2.3&#xff1a;非确定有限状态自动机 Nondeterministic fin…

go: go.mod file not found in current directory or any parent directory.如何解决?

这个错误表明你正在执行 go get 命令&#xff0c;但是当前目录或任何父目录中都找不到 go.mod 文件。这可能是因为你的项目还没有使用 Go Modules 进行管理。 要解决这个问题&#xff0c;有几种方法&#xff1a; go mod init <module-name> 其中 <module-name>…

Quill文档(五):Delta格式

富文本编辑器缺乏一种表达其自身内容的规范。直到最近&#xff0c;大多数富文本编辑器甚至不知道它们自己的编辑区域中有什么内容。这些编辑器只是传递用户的HTML&#xff0c;以及解析和解释这些HTML的负担。在任何给定的时间&#xff0c;这种解释都会与主要浏览器供应商的解释…

OpenCV与AI深度学习 | OpenCV中八种不同的目标追踪算法

本文来源公众号“OpenCV与AI深度学习”&#xff0c;仅用于学术分享&#xff0c;侵权删&#xff0c;干货满满。 原文链接&#xff1a;OpenCV中八种不同的目标追踪算法 目标跟踪作为机器学习的一个重要分支&#xff0c;加之其在日常生活、军事行动中的广泛应用&#xff0c;受到…

深入理解计算机系统 家庭作业 2.70

/* 网上很多都是错的,有些甚至题目都没读对 该题的意思是,x可以用多少位的补码表示. x -2时,最少用n2位补码就可以表示了 即 10 这道题求的是n 函数的核心思路: 用左右移位后的结果&一个n位的掩码就得到 x的最少位.移位没造出数字丢失时,x的最少位可以再通过移位还原成…