力扣题目链接[1]
请你设计并实现一个满足 LRU (最近最少使用) 缓存[2] 约束的数据结构。
实现 LRUCache 类:
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
提示:
1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 10^5
2 * 10^5
次 get 和 put思路:
本题借助Map的特性来实现LRU。根据MDN的描述,Map
对象保存键值对,并且能够记住键的原始插入顺序。因此插入的顺序就是最近使用的顺序。
当获取值时,直接get
获取,然后删除掉当前值,再重新插入到map
中,这样就实现了最近原则。
当设置值时,如果当前值已存在,则先删除再插入;如果当前缓存已满员,则删除掉最先插入的一条数据,再插入当前值。需要注意的是,可以通过以下方式来获取map
中的第一条值。
const map = new Map();
const first_value = map.keys().next().value;
MDN中说到,keys()
返回一个引用的 Iterator
对象。它包含按照 「顺序」 插入 Map
对象中每个元素的key值。获取迭代器的第一个键的值就是上述写法。同理,values()
也有类似的作用。
最终的代码如下:
/**
* @param {number} capacity
*/
var LRUCache = function(capacity) {
this.cache = new Map();
this.capacity = capacity;
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
if (this.cache.has(key)) {
let temp = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, temp);
return temp;
}
return -1;
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
if (this.cache.has(key)) {
this.cache.delete(key);
} else if (this.cache.size >= this.capacity) {
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)
*/
LRU算法思想在vue
的keep-alive
组件中有被使用。本题也是面试中常被问到的高频面试题。因此需要完全掌握。
更进一步的,也需要我们了解vue
的keep-alive
组件的源码是如何写的,学习优秀的源码,我们才可以走的更远。
[1]
力扣题目链接: https://leetcode-cn.com/problems/lru-cache/
[2]
LRU (最近最少使用) 缓存: https://baike.baidu.com/item/LRU