什么是 LRU ？
-
LRU （Least Recently Used）是最近最少使用算法；
-
它是根据时间维度来选择将要淘汰的元素，即删除掉最长时间没被访问的元素；
解题思路
-
LRU 缓存策略举例：
- 假设缓存大小为 4，依次打开了 gitlab、力扣、微信、QQ，缓存链表为 QQ -> 微信 -> 力扣 -> gitlab；
- 若此时切换到了「微信」，则缓存链表更新为 微信 -> QQ -> 力扣 -> gitlab；
- 若此时打开了腾讯会议，因为缓存已经满 4 个 ，所以要进行缓存淘汰机制，删除链表的最后一位 「gitlab」，则缓存链表更新为 腾讯会议 -> 微信 -> QQ -> 力扣；
-
本题用的是 map 迭代器，map 实现了 iterator，next 模拟链表的下一个指针，为了方便操作，这里将 map 第一个元素作为链表的最后一个元素；
let cache = new Map(); cache.set('a', 1); cache.set('b', 2); cache.set('c', 3); cache.keys(); // MapIterator {'a', 'b', 'c'} cache.keys().next().value; // a
复杂度
-
时间复杂度：对于 put 和 get 都是 O(1);
-
空间复杂度：O(capacity);
代码实现
TS
JS
// Vue3 的 keepalive 组件就用了这个 LRU 管理组件的缓存
class LRUCache {
capacity: number
map: Map<number, number> = new Map()
constructor(capacity: number) {
// 利用迭代器实现
this.map = new Map()
// 设置缓存最大个数
this.capacity = capacity
}
get(key: number): number {
if (this.map.has(key)) {
let value = this.map.get(key)
// 重新 set，相当于更新到 map 最后
this.map.delete(key)
this.map.set(key, value)
return value
}
return -1
}
put(key: number, value: number): void {
// 如果有，就删了再赋值
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)
}
}
}
// Vue3的keepalive组件就用了这个LRU管理组件的缓存
var LRUCache = function (capacity) {
this.map = new Map()
this.capacity = capacity
}
LRUCache.prototype.get = function (key) {
if (this.map.has(key)) {
let value = this.map.get(key)
// 重新set，相当于更新到 map最后
this.map.delete(key)
this.map.set(key, value)
return value
}
return -1
}
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)
}
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 215. 数组中的第 k 个最大元素
上一篇
评论
