图解LeetCode——146. LRU 缓存

简介: 图解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 ,则应该 逐出 最久未使用的关键字。

函数 getput 必须以 O(1) 的平均时间复杂度运行。

二、示例

2.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 <= 10^5
  • 最多调用 2 * 10^5getput

三、解题思路

根据题目描述,我们需要构造一个LRU缓存,那么我们需要解决两个问题:

问题1】实现对keyvalue的数据进行缓存。

问题2】实现LRU的能力,即:最近最少使用。

那么针对第一个问题,我们可以采用哈希表或者数组的方式进行数据存储,因为本题的提示部分已经指出key值是在[0, 10000]区间内的,并不存在负数,所以为了提升执行速度,我们选择数组作为底层的存储结构。其中,需要注意的是,存储的value是下面要介绍的双向链表中的Node节点

那么针对第二个问题,我们可以采用双向链表的方式进行支持,那么为什么是双向链表呢?因为当调用lRUCache.get()lRUCache.set()方法对某个Node进行操作的时候,我们需要将这个Node放到链表的尾部,这样,就需要操作该Node节点的前置节点后置节点,为了便于这种操作,所以我们采用双向链表。执行步骤如下所示:

步骤1】断开PreNodeNode的链接关系;

步骤2】断开NextNodeNode的链接关系;

步骤3】链接PreNodeNextNode

步骤4】将Node放到链表尾部;

那么这里还有一个小细节,就是如果待移动的节点在头节点,那么我们还需要进行特殊的判断(因为头节点没有前置节点PreNode),而同样的,如果待删除的节点是尾节点,那么我们也需要进行特殊的判断(因为尾节点没有后置节点NextNode)。为了统一处理逻辑,我们可以通过创建虚拟的头尾节点来解决这个问题,即:

虚拟头节点】Node head = new Node(-1, -1);

虚拟尾节点】Node tail = new Node(-2, -1);

初始情况下head.next = tail;    tail.pre = head;

由于我们可以知道LRU链表容量的,所以当超出这个容量的时候,就将整个链表中,第一个节点删除即可(不包含虚拟收尾节点),并将哈希表/数组中相应key对应的value置为null;以上就是这道题的解题思路,为了便于大家理解,我们通过创建2节点容量的LRU,具体看一下具体的处理过程,请见下图所示:

四、代码实现

class LRUCache {
    Node[] hashTable; // 哈希表
    int capacity = 0, count = 0;
    Node head, tail;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        hashTable = new Node[10001];
        head = new Node(-1, -1); // 虚拟头节点
        tail = new Node(-2, -1); // 虚拟尾节点
        head.next = tail;
        tail.pre = head;
    }
    public int get(int key) {
        Node node;
        if ((node = hashTable[key]) == null) return -1; // 如果不存在,直接返回-1
        moveNode(node); // 将node节点移动到末尾(位置是tail节点的pre节点)
        return node.value;
    }
    public void put(int key, int value) {
        Node node;
        if ((node = hashTable[key]) != null) { // 已存在节点,直接修改value值
            node.value = value;
        } else { // 不存在节点,则新建Node
            if (count < capacity) { // 没有到达容量上限
                count++;
            } else { // 超出容量上限,则需要删除“最近最少使用”的节点
                hashTable[head.next.key] = null;
                delNode(head.next);
            }
            node = new Node(key, value);
            hashTable[key] = node;
        }
        moveNode(node); // 将node节点移动到末尾
    }
    // 删除节点操作
    public void delNode(Node node) {
        if (node.pre == null || node.next == null) return;
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
    // 将节点移动到“末尾”操作(位置是tail节点的pre节点)
    public void moveNode(Node node) {
        if (tail.pre == node) return; // 如果已经是“末尾”节点,则不操作
        delNode(node); // 删除该节点的前后关联,下面会进行重新关联操作
        tail.pre.next = node;
        node.pre = tail.pre;
        node.next = tail;
        tail.pre = node;
    }
    // 双向链表结构
    class Node {
        public int key, value;
        public Node pre, next;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}

今天的文章内容就这些了:

写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享

更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享,每天更新」

相关文章
|
2月前
|
缓存 算法 数据挖掘
深入理解缓存更新策略:从LRU到LFU
【10月更文挑战第7天】 在本文中,我们将探讨计算机系统中缓存机制的核心——缓存更新策略。缓存是提高数据检索速度的关键技术之一,无论是在硬件还是软件层面都扮演着重要角色。我们会详细介绍最常用的两种缓存算法:最近最少使用(LRU)和最少使用频率(LFU),并讨论它们的优缺点及适用场景。通过对比分析,旨在帮助读者更好地理解如何选择和实现适合自己需求的缓存策略,从而优化系统性能。
66 3
|
2月前
|
缓存 分布式计算 NoSQL
大数据-47 Redis 缓存过期 淘汰删除策略 LRU LFU 基础概念
大数据-47 Redis 缓存过期 淘汰删除策略 LRU LFU 基础概念
82 2
|
4月前
|
缓存 算法 前端开发
深入理解缓存淘汰策略:LRU和LFU算法的解析与应用
【8月更文挑战第25天】在计算机科学领域,高效管理资源对于提升系统性能至关重要。内存缓存作为一种加速数据读取的有效方法,其管理策略直接影响整体性能。本文重点介绍两种常用的缓存淘汰算法:LRU(最近最少使用)和LFU(最不经常使用)。LRU算法依据数据最近是否被访问来进行淘汰决策;而LFU算法则根据数据的访问频率做出判断。这两种算法各有特点,适用于不同的应用场景。通过深入分析这两种算法的原理、实现方式及适用场景,本文旨在帮助开发者更好地理解缓存管理机制,从而在实际应用中作出更合理的选择,有效提升系统性能和用户体验。
222 1
|
5月前
|
缓存 Python
在Python中,`functools`模块提供了一个非常有用的装饰器`lru_cache()`,它实现了最近最少使用(Least Recently Used, LRU)缓存策略。
在Python中,`functools`模块提供了一个非常有用的装饰器`lru_cache()`,它实现了最近最少使用(Least Recently Used, LRU)缓存策略。
|
4月前
|
存储 缓存 Java
|
4月前
|
存储 缓存 算法
Python 从零开始实现一个简单的LRU缓存
Python 从零开始实现一个简单的LRU缓存
47 0
|
6月前
|
缓存 算法 索引
LeetCode146:LRU缓存
LeetCode146:LRU缓存
48 1
|
5月前
|
缓存 算法 前端开发
前端 JS 经典:LRU 缓存算法
前端 JS 经典:LRU 缓存算法
101 0
|
7月前
|
缓存 算法 Java
数据结构~缓存淘汰算法--LRU算法(Java的俩种实现方式,万字解析
数据结构~缓存淘汰算法--LRU算法(Java的俩种实现方式,万字解析
|
3天前
|
存储 缓存 NoSQL
解决Redis缓存数据类型丢失问题
解决Redis缓存数据类型丢失问题
117 85