请实现一个 LRU 缓存
参考答案
需求:容量上限,get 命中刷新为最新,put 超容量淘汰最久未用。要求 O(1)。
class LRU {
constructor(cap) { this.cap = cap; this.map = new Map(); }
get(k) {
if (!this.map.has(k)) return -1;
const v = this.map.get(k);
this.map.delete(k); this.map.set(k, v); // 刷新到末尾
return v;
}
put(k, v) {
if (this.map.has(k)) this.map.delete(k);
this.map.set(k, v);
if (this.map.size > this.cap) {
this.map.delete(this.map.keys().next().value); // 淘汰最旧
}
}
}
原理
Map 保证插入顺序;delete + set 把键移到末尾(最近使用),首个键即最久未使用。
若手写哈希表 + 双向链表:get 时把节点移到头部,put 超限删尾节点,同样 O(1)。