数据结构与算法之链表: LeetCode 146. LRU 缓存 (Ts版)

news/2025/1/16 14:53:15/

LRU 缓存

  • https://leetcode.cn/problems/lru-cache/description/

描述

  • 请你设计并实现一个满足 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 <= 1 0 5 10^5 105
  • 最多调用 2 * 1 0 5 10^5 105 次 get 和 put

Typescript 版算法实现


1 ) 方案1: 基于Map

class LRUCache {public cache: Map<number, any>public max: numberconstructor(capacity: number) {this.cache = new Map()this.max = capacity}get(key: number): number {if (!this.cache.has(key)) return -1const tmp = this.cache.get(key)this.cache.delete(key)this.cache.set(key, tmp)return tmp}put(key: number, value: number): void {if(this.cache.has(key)) {this.cache.delete(key)} else if(this.cache.size >= this.max) {// 新增时的淘汰机制this.cache.delete(this.cache.keys().next().value)}this.cache.set(key, value)}
}/*** Your LRUCache object will be instantiated and called as such:* var obj = new LRUCache(capacity)* var param_1 = obj.get(key)* obj.put(key,value)*/

2 ) 方案2: 哈希表 + 双向链表

class DLinkedNode {key: number;value: number;prev: DLinkedNode | null;next: DLinkedNode | null;constructor(key: number = 0, value: number = 0) {this.key = key;this.value = value;this.prev = null;this.next = null;}
}class LRUCache {private size: number;private capacity: number;private cache: Map<number, DLinkedNode>;private head: DLinkedNode;private tail: DLinkedNode;constructor(capacity: number) {this.size = 0;this.capacity = capacity;this.cache = new Map();this.head = new DLinkedNode();this.tail = new DLinkedNode();this.head.next = this.tail;this.tail.prev = this.head;}private addToHead(node: DLinkedNode): void {node.prev = this.head;node.next = this.head.next;this.head.next!.prev = node;this.head.next = node;}private removeNode(node: DLinkedNode): void {node.prev!.next = node.next;node.next!.prev = node.prev;}private moveToHead(node: DLinkedNode): void {this.removeNode(node);this.addToHead(node);}private removeTail(): DLinkedNode {const node = this.tail.prev!;this.removeNode(node);return node;}public get(key: number): number {if (!this.cache.has(key)) {return -1;}const node = this.cache.get(key)!;this.moveToHead(node);return node.value;}public put(key: number, value: number): void {if (!this.cache.has(key)) {const newNode = new DLinkedNode(key, value);this.cache.set(key, newNode);this.addToHead(newNode);this.size++;if (this.size > this.capacity) {const removedNode = this.removeTail();this.cache.delete(removedNode.key);this.size--;}} else {const node = this.cache.get(key)!;node.value = value;this.moveToHead(node);}}
}/*** Your LRUCache object will be instantiated and called as such:* var obj = new LRUCache(capacity)* var param_1 = obj.get(key)* obj.put(key,value)*/

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

相关文章

容器技术全面攻略:Docker的硬核玩法

文章背景 想象一下&#xff0c;一个项目终于要上线了&#xff0c;结果因为环境配置不一致&#xff0c;测试服务器一切正常&#xff0c;生产环境却宕机了。这是开发者噩梦的开始&#xff0c;也是Docker救世主角色的登场&#xff01;Docker的出现颠覆了传统环境配置的方式&#…

【kubernetes】K8S节点状态的维护

1 节点状态 节点是K8S集群中的一类重要资源&#xff0c;节点的状态通常可以作为判断集群异常的重要手段。 为了展示节点在各方面的健康程度&#xff0c;在kubectl describe node k8s-master的输出结果中的Conditions部分可以查看k8s-master节点的一些状态数据&#xff1a; N…

【Linux】8.Linux基础开发工具使用(2)

文章目录 1. Linux编译器-gcc/g使用关于sudo1.1 背景知识1.2 gcc如何完成1.2.1 预处理(进行宏替换)1.2.2 编译&#xff08;生成汇编&#xff09;1.2.3 汇编&#xff08;生成机器可识别代码&#xff09;1.2.4 连接&#xff08;生成可执行文件或库文件&#xff09;1.2.5 总结 1.3…

OmniAudio-2.6B 简介与音频转文本实践

OmniAudio-2.6B 是一个基于 Transformer 的先进语音识别模型&#xff0c;具有强大的音频转文本能力。它利用大规模预训练和多语言支持&#xff0c;为离线和在线语音处理提供高精度的解决方案。 一、OmniAudio-2.6B 的原理 1. 核心技术 Transformer 架构&#xff1a;OmniAudio…

极客说|Azure AI Agent Service 结合 AutoGen/Semantic Kernel 构建多智能体解决⽅案

作者&#xff1a;卢建晖 - 微软高级云技术布道师 「极客说」 是一档专注 AI 时代开发者分享的专栏&#xff0c;我们邀请来自微软以及技术社区专家&#xff0c;带来最前沿的技术干货与实践经验。在这里&#xff0c;您将看到深度教程、最佳实践和创新解决方案。关注「极客说」&am…

ParcelFileDescriptor+PdfRenderer在Android渲染显示PDF文件

ParcelFileDescriptor 是一个非常重要的类&#xff0c;用于表示一个文件描述符&#xff08;File Descriptor&#xff0c;简称 FD&#xff09;&#xff0c;它可以让文件或数据通过进程间通信&#xff08;IPC&#xff09;进行共享。 1. 基本概念 ParcelFileDescriptor 是 andro…

【行空板K10】上传温湿度信息到EasyIoT平台

目录 引言 EasyIoT平台 程序编写 测试结果 结语 引言 今天测试一下使用行空板K10上传数据到EasyIoT平台。这个平台是DFRobot自由的物联网云平台&#xff0c;也是Mind支持的4个MQTT平台之一。 EasyIoT平台 EasyIoT平台的优点是非常简单&#xff0c;没有阿里云、华为云那…

蓝桥杯刷题第二天——背包问题

题目描述 有N件物品和一个容量是V的背包。每件物品只能使用一次。第i件物品的体积是Vi价值是Wi。 求解将哪些物品装入背包&#xff0c;可使这些物品的总体积不超过背包容量&#xff0c;且总价值最大。 输出最大价值。 输入格式 第一行两个整数&#xff0c;N&#xff0c;V&am…