【LeetCode刷题】146. LRU 缓存

请你设计并实现一个满足  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

思路：这道题的难点在于记录最近最少使用，使用map可以满足get的O(1)，但是无法记录最近最少使用的数据；如果使用数组，删除/增加的时间复杂度则是O(n)，也不满足。

使用哈希表 + 双向链表可以满足删除/增加的时间复杂度为O(1)。

这个图太形象了。

（1）双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。

（2）哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。

（3）对于 get 操作，首先判断 key 是否存在：

        （a）如果 key 不存在，则返回 −1；

        （b）如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。

（3）对于 put 操作，首先判断 key 是否存在：

        （a）如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；

        （b）如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。

思路很清晰

class LRUCache {
public:
    LRUCache(int capacity) {

    }
    
    int get(int key) {

    }
    
    void put(int key, int value) {

    }
};

/**
 * 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);
 */

一步步实现：

（1）定义双链表

struct DLinkedNode {
    int key, value;             // k-v
    DLinkedNode* prev;          // 前向指针
    DLinkedNode* next;          // 后向指针
    // 两个构造函数
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
    DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

（2）在LRUCache类中添加成员属性：哈希表+双向链表

class LRUCache {
public:
    // 新加的
    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode* head;            // 伪头节点，不存数据
    DLinkedNode* tail;            // 伪尾节点，不存数据
    int size;                     // 当前存储的数量，当size==capacity时，要移出数据了
    int capacity;                 // 容量

    // 实现构造函数
    LRUCache(int _capacity): capacity(_capacity), size(0) {
        // 使用伪头节点和伪尾节点，不存数据
        head = new DLinkedNode();
        tail = new DLinkedNode();
        // 开始时一个数据都没有
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {

    }
    
    void put(int key, int value) {

    }
};

（3）实现双向链表中的【在头部添加数据】、【任意位置删除数据】、【数据移动到头部】、【从尾部删除数据】

在头部添加数据

    // 在头部添加数据
    void addToHead(DLinkedNode* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }

任意位置删除数据

    // 任意位置删除数据
    void removeNode(DLinkedNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

数据移动到头部

    // 移动数据到头部
    void moveToHead(DLinkedNode* node) {
        removeNode(node);
        addToHead(node);
    }

从尾部删除数据

    // 从尾部删除数据
    DLinkedNode* reoveTail() {
        DLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }

（4）实现get函数

如果不存在直接返回-1，存在的话，先通过哈希表定位，再移动到头部

    int get(int key) {
        // 不存在
        if (cache.count(key) == 0) {
            return -1;
        }
        // 通过哈希找到，移动到头部
        DLinkedNode* node = cache[key];
        moveToHead(node);
        return node->value;
    }

（5）实现put函数

如果key不存在，则创建一个节点，注意size==capacity的情况，此时删除队尾数据

靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。

如果存在，修改value，再将该节点移动到队头

 void put(int key, int value) {
        // 不存在
        if (cache.count(key) == 0) {
            DLinkedNode* node = new DLinkedNode(key, value);
            cache[key] = node;          // 添加到哈希表中
            addToHead(node);            // 移动到队头
            size++;
            if (size > capacity) {
                DLinkedNode* removeNode = reoveTail();  // 删除尾部数据
                cache.erase(removeNode->key);           // 删除哈希中的数据
                delete removeNode;
                size--; 
            }
        } else {
            DLinkedNode* node = cache[key];
            node->value = value;
            moveToHead(node);               // 移到队头
        }
    }

全部代码实现

struct DLinkedNode {
    int key, value;             // k-v
    DLinkedNode* prev;          // 前向指针
    DLinkedNode* next;          // 后向指针
    // 两个构造函数
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
    DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
public:
    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int size;
    int capacity;


    LRUCache(int _capacity): capacity(_capacity), size(0) {
        // 使用伪头节点和伪伪节点，不存数据
        head = new DLinkedNode();
        tail = new DLinkedNode();
        // 开始时一个数据都没有
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        // 不存在
        if (cache.count(key) == 0) {
            return -1;
        }
        // 通过哈希找到，移动到头部
        DLinkedNode* node = cache[key];
        moveToHead(node);
        return node->value;
    }
    
    void put(int key, int value) {
        // 不存在
        if (cache.count(key) == 0) {
            DLinkedNode* node = new DLinkedNode(key, value);
            cache[key] = node;          // 添加到哈希表中
            addToHead(node);            // 移动到队头
            size++;
            if (size > capacity) {
                DLinkedNode* removeNode = reoveTail();  // 删除尾部数据
                cache.erase(removeNode->key);           // 删除哈希中的数据
                delete removeNode;
                size--; 
            }
        } else {
            DLinkedNode* node = cache[key];
            node->value = value;
            moveToHead(node);               // 移到队头
        }
    }

    // 在头部添加数据
    void addToHead(DLinkedNode* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }

    // 任意位置删除数据
    void removeNode(DLinkedNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    // 移动数据到头部
    void moveToHead(DLinkedNode* node) {
        removeNode(node);
        addToHead(node);
    }

    // 从尾部删除数据
    DLinkedNode* reoveTail() {
        DLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }


};

/**
 * 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);
 */

参考：【字节一面】 LRU Cache 实现剖析_哔哩哔哩_bilibili

链接：. - 力扣（LeetCode）

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

JVM 第二部分-3（对象，直接内存）

JVM 第二部分-3（对象，直接内存）

对象 对象的实例化 创建对象的方式 new 对象 变形1&#xff1a;使用类的静态方法获得对象变形2&#xff1a;xxxBuilder、xxxFactory的静态方法 反射 Class的newInstance()&#xff1a;反射的方式&#xff0c;只能调用空参的构造器&#xff0c;权限必须是publicConstructor的ne…
阅读更多...
文献速递：帕金森的疾病分享--多模态机器学习预测帕金森病

文献速递：帕金森的疾病分享--多模态机器学习预测帕金森病

文献速递&#xff1a;帕金森的疾病分享–多模态机器学习预测帕金森病 Title 题目 Multi-modality machine learning predicting Parkinson’s disease 多模态机器学习预测帕金森病 01 文献速递介绍 对于渐进性神经退行性疾病&#xff0c;早期和准确的诊断是有效开发和使…
阅读更多...
Thumbnailator简介和示例

Thumbnailator简介和示例

背景 对于javaweb服务端开发人员&#xff0c;图片资源的管理总是绕不开的一环。很多网站上都会提供上传图片这个功能&#xff0c;而现代数码设备拍摄出来的都是高清图片&#xff0c;分辨率很高&#xff0c;占用的空间也很大。物理存储的问题还算容易解决&#xff0c;但是网络带…
阅读更多...
maven的私服

maven的私服

什么是maven的私服就是把自己写的工具类共享给别人这样大家都能用到你写的工具类不用重复写提示效率 maven的上传与下载示意图 1.什么是发行版本&#xff1f;发行版本指定的是功能稳定可以共大家使用的版本 2.什么是快照版本&#xff1f;快照版本指定的是指正在开发的版本 3…
阅读更多...
[⑥5G NR]: 无线接口协议，信道映射学习

[⑥5G NR]: 无线接口协议，信道映射学习

5G系统整体包括核心网、接入网以及终端部分&#xff0c;接入网与终端间通过无线空口协议栈进行连接。无线接口可分为三个协议层&#xff1a;物理层&#xff08;L1&#xff09;、数据链路层&#xff08;L2&#xff09;和网络层&#xff08;L3&#xff09;。 L1&#xff1a;物理…
阅读更多...
【数据结构】：单链表之头插法和尾插法（动图+图解）

【数据结构】：单链表之头插法和尾插法（动图+图解）

头插法和尾插法 一、头插法&#x1f4a4;思考一&#xff1a;头插法的核心是什么❓❗❗ 重点一&#xff1a;以带头结点方式实现头插法❗❗ 重点二&#xff1a;以不带头结点方式实现头插法 二、尾插法&#x1f4a4;思考二&#xff1a;尾插法的核心是什么❓❗❗ 重点三&#xff1a…
阅读更多...
PostgreSQL中int类型达到上限的一些处理方案

PostgreSQL中int类型达到上限的一些处理方案

使用int类型作为表的主键在pg中是很常见的情况&#xff0c;但是pg中int类型的范围在-2147483648到2147483647&#xff0c;最大只有21亿&#xff0c;这个在一些大表中很容易就会达到上限。一旦达到上限&#xff0c;那么表中便没办法在插入数据了&#xff0c;这个将会是很严重的问…
阅读更多...
k8s分布式图床（k8s，metricsapi，vue3+ts）

k8s分布式图床（k8s，metricsapi，vue3+ts）

image-manage 图像管理应用 图像管理应用提供了一个方便管理图片的平台&#xff0c;支持单机和Kubernetes集群部署。请确保您至少拥有一个MySQL数据库和一个Redis数据库&#xff0c;以及一个至少为Kubernetes 1.29版本的集群&#xff08;如果选择集群部署&#xff09;。 文档…
阅读更多...
Linux开发工具vim

Linux开发工具vim

目录 1. vim的基本概念2. vim的基本操作3. vim正常模式命令集1. 插入模式2. 从插入模式切换为命令模式3. 移动光标4. 删除文字5.复制6. 替换7. 撤销上一次操作8. 更改9. 跳至指定的行 4. vim末行模式命令集1. 列出行号2. 跳到文件中的某一行5. 查找字符6. 保存文件7. 离开vim 1…
阅读更多...
Java多线程导出Excel示例

Java多线程导出Excel示例

在之前的Java多线程导入Excel示例中演示了如何通过多线程的方式导入Excel&#xff0c;下面我们再来看下怎么通过多线程的方式导出Excel 还是直接上代码 首先是Controller import com.sakura.base.service.ExcelService; import org.springframework.beans.factory.annotation.…
阅读更多...
【数据分享】2000~2023年MOD15A2H 061 光合有效辐射分数FPAR数据集

【数据分享】2000~2023年MOD15A2H 061 光合有效辐射分数FPAR数据集

​各位同学们好&#xff0c;今天和大伙儿分享的是2000~2023年MOD15A2H 061 光合有效辐射分数FPAR数据集。如果大家有下载处理数据等方面的问题&#xff0c;可以评论或私信。 Myneni, R., Y. Knyazikhin, T. Park. MODIS/Terra Leaf Area Index/FPAR 8-Day L4 Global 500m SIN G…
阅读更多...
网络工程师笔记6

网络工程师笔记6

ICMP协议 Internet控制报文协议ICMP(InternetControlMessage Protocol)是网络层的一个重要协议。ICMP协议用来在网络设备间传递各种差错和控制信息&#xff0c;它对于收集各种网络信息、诊断和排除各种网络故障具有至关重要的作用。使用基于ICMP的应用时&#xff0c;需要对ICMP…
阅读更多...
live555源码学习（1）

live555源码学习（1）

1 基础组件 live项目主要包含了四个基础库、程序入口类&#xff08;mediaServer&#xff09;和测试程序&#xff08;testProgs&#xff09;。四个基础库是UsageEnvironment、BasicUsageEnvironment、groupsock和liveMedia UsageEnvironment 抽象了两个类UsageEnvironment和T…
阅读更多...
基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的钢材表面缺陷检测系统（Python+PySide6界面+训练代码）

基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的钢材表面缺陷检测系统（Python+PySide6界面+训练代码）

摘要&#xff1a;开发钢材表面缺陷检测系统对于保障制造质量和提高生产效率具有关键作用。本篇博客详细介绍了如何运用深度学习构建一个钢材表面缺陷检测系统&#xff0c;并提供了完整的实现代码。该系统基于强大的YOLOv8算法&#xff0c;并对比了YOLOv7、YOLOv6、YOLOv5&#…
阅读更多...
Grid-Based Continuous Normal Representation for Anomaly Detection 论文阅读

Grid-Based Continuous Normal Representation for Anomaly Detection 论文阅读

Grid-Based Continuous Normal Representation for Anomaly Detection 论文阅读 摘要简介方法3.1 Normal Representation3.2 Feature Refinement3.3 Training and Inference 4 实验结果5 总结 文章信息&#xff1a; 原文链接&#xff1a;https://arxiv.org/abs/2402.18293 源码…
阅读更多...
应用层DDoS防护：理解、必要性与实现策略

应用层DDoS防护：理解、必要性与实现策略

一、应用层简介 应用层&#xff0c;也称作第七层&#xff0c;是OSI&#xff08;开放系统互联&#xff09;模型中的最高层。在这一层&#xff0c;数据以特定的应用程序协议格式进行传输&#xff0c;如HTTP、FTP、SMTP等。应用层的主要职责是为用户提供网络服务&#xff0c;如文…
阅读更多...
Android Gradle开发与应用 (四) : Gradle构建与生命周期

Android Gradle开发与应用 (四) : Gradle构建与生命周期

1. 前言 前几篇文章&#xff0c;我们对Gradle中的基本知识&#xff0c;包括Gradle项目结构、Gradle Wrapper、GradleUserHome、Groovy基础语法、Groovy语法概念、Groovy闭包等知识点&#xff0c;这篇文章我们接着来介绍Gradle构建过程中的知识点。 2. Project : Gradle中构建…
阅读更多...
python61-Python的循环之for-in循环遍历列表和元组

python61-Python的循环之for-in循环遍历列表和元组

在使用 for-in 循环遍历列表和元组时&#xff0c;列表或元组有几个元素&#xff0c;for-in 循环的循环体就执行几次&#xff0c;针对每个元素执行一次&#xff0c;循环计数器会依次被赋值为元素的值&#xff0c;如下代码使用 for-in 循环遍历元组。 # !/usr/bin/env python# -…
阅读更多...
C# Socket通信从入门到精通（21）——TCP发送文件与接收文件 C#代码实现

C# Socket通信从入门到精通（21）——TCP发送文件与接收文件 C#代码实现

1、前言 我们在开发上位机软件的过程中经常需要发送文件，本文就是介绍如何利用tcp客户端发送文件、tcp服务器端接收文件，而且本文介绍的方法可以自动发送一个文件夹下的所有子目录以及所有文件，经验来自于实际项目，具备非常有价值的参考意义！ 2、发送文件以及C#代码 被发…
阅读更多...
基于React俄罗斯方块h5小游戏源码响应式支持PC+手机

基于React俄罗斯方块h5小游戏源码响应式支持PC+手机

俄罗斯方块是一款广受欢迎的经典游戏&#xff0c;许多编程语言都热衷于实现它。在JavaScript中&#xff0c;也有许多版本。 我的目标是使用React框架来实现这个游戏。 地 址 &#xff1a; runruncode.com/vue/19701.html 游戏的架构采用了React和Redux&#xff0c;为了提高性…
阅读更多...
最新文章

Copyright @ 2022~2023