题目描述
请你设计并实现一个满足 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);
}
};
has(key)检查缓存中是否有key。delete(key)删除旧的key-value对。set(key, value)插入新的key-value对。size获取当前缓存的大小。keys()获取所有的key，然后使用迭代器获取第一个key。delete(key)删除最久未使用的key-value对。
注意
当我们调用this.map.keys().next().value时，我们实际上是在获取第一个插入Map的键。
在get方法中，如果键存在，我们先从Map中删除该键值对，然后重新插入，这实际上将该键值对移动到了最近使用的位置。
在put方法中，如果键已经存在，我们先从Map中删除该键值对，然后重新插入新的键值对。如果插入后Map的大小超过了容量，我们会删除第一个键值对，也就是最久未使用的键值对。
所以，这段代码实际上是按照插入顺序来确定最久未使用的键值对的。如果一个键值对在Map中被更新（通过get或put方法），它会被移动到Map的末尾，这意味着它被视为最近使用的。
因此，this.map.delete(this.map.keys().next().value);这行代码确实是在删除最久未使用的键值对，因为它是第一个插入的，并且在之前的get或put操作中没有被更新过。
代码能够以O(1)的平均时间复杂度运行get和put操作，并且正确实现了LRU缓存策略。
案例分析
让我们通过一个具体的例子来分析您提供的LRU缓存代码的工作方式：
假设我们创建了一个容量为2的LRU缓存：
var cache = new LRUCache(2);
然后我们进行以下操作：
cache.put(1, 1);缓存现在包含{1=1}。cache.put(2, 2);缓存现在包含{1=1, 2=2}。cache.get(1);返回1，缓存现在变为{2=2, 1=1}，因为1被访问了，所以它被移到了最近使用的位置。cache.put(3, 3);缓存满了，需要删除最久未使用的元素，也就是2，所以缓存变为{1=1, 3=3}。cache.get(2);返回-1，因为2已经被删除了。cache.put(4, 4);缓存再次满了，删除最久未使用的元素1，缓存变为{3=3, 4=4}。cache.get(1);返回-1，因为1已经被删除了。cache.get(3);返回3，缓存变为{4=4, 3=3}，因为3被访问了，所以它被移到了最近使用的位置。cache.get(4);返回4，缓存变为{3=3, 4=4}，因为4被访问了，所以它被移到了最近使用的位置。
下面是每次操作后缓存的状态：
- 初始状态：
{}（空缓存） - 插入
1：{1=1} - 插入
2：{1=1, 2=2} - 访问
1：{2=2, 1=1}（1被移到最近使用的位置） - 插入
3：{1=1, 3=3}（2被删除） - 访问
2：返回-1（2不存在） - 插入
4：{3=3, 4=4}（1被删除） - 访问
1：返回-1（1不存在） - 访问
3：{4=4, 3=3}（3被移到最近使用的位置） - 访问
4：{3=3, 4=4}（4被移到最近使用的位置）