当前位置：首页 > article >正文

LeetCode LRU 缓存

article 2024/10/20 18:49:25

题目描述

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

题目分析

LRU 算法就是一种缓存淘汰策略，原理不难，但是面试中写出没有 bug 的算法比较有技巧，需要对数据结构进行层层抽象和拆解。

计算机的缓存容量有限，如果缓存满了就要删除一些内容，给新内容腾位置。但问题是，删除哪些内容呢？我们肯定希望删掉哪些没什么用的缓存，而把有用的数据继续留在缓存里，方便之后继续使用。那么，什么样的数据，我们判定为「有用的」的数据呢？

LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used，也就是说我们认为最近使用过的数据应该是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。

举个简单的例子，安卓手机都可以把软件放到后台运行，比如我先后打开了「设置」「手机管家」「日历」，那么现在他们在后台排列的顺序是这样的：
在这里插入图片描述
但是这时候如果我访问了一下「设置」界面，那么「设置」就会被提前到第一个，变成这样：

假设我的手机只允许我同时开 3 个应用程序，现在已经满了。那么如果我新开了一个应用「时钟」，就必须关闭一个应用为「时钟」腾出一个位置，关那个呢？

按照 LRU 的策略，就关最底下的「手机管家」，因为那是最久未使用的，然后把新开的应用放到最上面：

首先要接收一个 capacity 参数作为缓存的最大容量，然后实现两个 API，一个是 put(key, val) 方法存入键值对，另一个是 get(key) 方法获取 key 对应的 val，如果 key 不存在则返回 -1。

注意哦，get 和 put 方法必须都是 O(1) 的时间复杂度，我们举个具体例子来看看 LRU 算法怎么工作。

/* 缓存容量为 2 */
LRUCache cache = new LRUCache(2);
// 圆括号表示键值对 (key, val)

cache.put(1, 1);
// cache = [(1, 1)]

cache.put(2, 2);
// cache = [(1, 1),(2, 2)]

cache.get(1);       // 返回 1
// cache = [(2, 2),(1, 1)]
// 解释：因为最近访问了键 1，所以重新插入
// 返回键 1 对应的值 1

cache.put(3, 3);
// cache = [(1, 1),(3, 3)]
// 解释：缓存容量已满，需要删除内容空出位置
// 优先删除久未使用的数据，也就是第一个的数据
// 然后把新的数据插入末尾

cache.get(2);       // 返回 -1 (未找到)
// cache = [(1, 1),(3, 3)]
// 解释：cache 中不存在键为 2 的数据

cache.put(1, 4);    
// cache = [(3, 3)，(1, 4)]

所以代码思路为

用map保存key
get 有key 缓存value 删掉key 再set一遍
put 有key 删掉重新set 超出内存删掉第一个key

代码

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.capacity = capacity;
    this.map = new Map();
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if(this.map.has(key)){
        let temp=this.map.get(key)
         this.map.delete(key);
         this.map.set(key, temp);
         return temp
    }else{
        return -1
    }
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if(this.map.has(key)){
        this.map.delete(key);
    }
    this.map.set(key,value);
    if(this.map.size > this.capacity){
     
        this.map.delete(this.map.keys().next().value);
    }
};

代码分析

LRUCache 构造函数

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.capacity = capacity; // 缓存容量
    this.map = new Map(); // 使用Map来存储key-value对
};

capacity 是缓存的最大容量。
map 是一个哈希表，用来存储缓存中的键值对。

get 方法

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if(this.map.has(key)){
        let temp = this.map.get(key); // 取出key对应的value
        this.map.delete(key); // 删除旧的key-value对
        this.map.set(key, temp); // 重新插入key-value对，这样key就移动到了最近使用的位置
        return temp;
    } else {
        return -1; // 如果key不存在，返回-1
    }
};

has(key) 检查缓存中是否有key。
get(key) 获取key对应的value。
delete(key) 删除旧的key-value对。
set(key, value) 插入新的key-value对，这样key就移动到了最近使用的位置。

put 方法

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if(this.map.has(key)){
        this.map.delete(key); // 如果key已经存在，先删除旧的key-value对
    }
    this.map.set(key, value); // 插入新的key-value对
    if(this.map.size > this.capacity){
        // 如果当前缓存的容量超过了限制，需要删除最久未使用的key-value对
        // 使用迭代器获取第一个key，然后删除对应的key-value对
        this.map.delete(this.map.keys().next().value);
    }
};