零 标题:算法(leetcode,附思维导图 + 全部解法)300题之(146)LRU 缓存
一 题目描述
二 解法总览(思维导图)
三 全部解法
1 方案1
1)代码:
// 则 先删该key、接着把该key放到map的最后 —— 表示最近使用过该key!
if (map.has(key)) {
map.delete(key);
map.set(key, value);
return;
}
// 边界3:put操作,若 当前已经放不下了(即 curCapacity >= capacity ),
// 则 删除map的第一个key 且 将新key放到map的最后 —— 表示最近使用过该key!
if (curCapacity >= capacity) {
for (const [key, val] of map) {
map.delete(key);
break;
}
map.set(key, value);
}
// 边界4:put操作,若 当前放得下(即 curCapacity < capacity ),
// 则 直接将新key放到map的最后 —— 表示最近使用过该key 且 this.curCapacity++ 。
else {
map.set(key, value);
this.curCapacity++;
}
// 注:以上 5行 ,可以合并成如下 2行 (但为了可读性,可分拆为 if、else 2分支):
// }
// map.set(key, value);
};
2 方案2
1)代码:
// 方案2 “自己。哈希表 + 双向链表”。
// 参考:
// 1)https://leetcode.cn/problems/lru-cache/solution/146-lru-huan-cun-ji-zhi-by-chen-wei-f-tl1n/
// 思路:
// 1)重点实现 ListNode 和 LRUCache 2个类。
// 2)get、put操作:
// 根据当前情况进行 curCapacity、map、各种节点 的信息变更即可,详见代码的实现。
//双向链表的单个节点
class ListNode {
constructor(key, value) {
this.key = key;
this.value = value;
//指向后一个节点
this.next = null;
//指向前一个节点
this.prev = null;
}
}
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.curCapacity = 0;
this.map = new Map();
this.dummyHead = new ListNode();
this.dummyTail = new ListNode();
this.dummyHead.next = this.dummyTail;
this.dummyTail.prev = this.dummyHead;
}
get(key) {
const {map = new Map()} = this,
node = map.get(key);
// 没找到
if (!node) {
return - 1;
}
// 找到,将该节点挪到头部,并返回相应的值
this.moveToHead(node);
return node.value;
}
put(key, value) {
const {map = new Map()} = this,
node = map.get(key);
if (!node) {
// 不存在该节点,则进行节点的创建。
const newNode = new ListNode(key, value);
map.set(key, newNode);
// 加入头结点(addToHead),而不是挪(moveToHead)
this.addToHead(newNode);
this.curCapacity++;
// 边界:超容量了,得删除
if (this.curCapacity > this.capacity) {
this.removeLRUItem();
}
}
else {
// 存在该节点,更新其值 并 将该节点挪到头部
node.value = value;
this.moveToHead(node);
}
}
moveToHead(node) {
//从链表中删除该节点 并 将该节点添加至头结点
this.removeFromList(node);
this.addToHead(node);
}
// 节点的删除(本质:指针指向的变更)
removeFromList(node) {
let nodePre = node.prev,
nodeNext = node.next;
nodePre.next = nodeNext;
nodeNext.prev = nodePre;
}
// 节点加入链表头部 的指针操作
addToHead(node) {
const {dummyHead = null} = this,
dummyHeadNext = dummyHead.next;
node.prev = dummyHead;
node.next = dummyHeadNext;
dummyHeadNext.prev = node;
dummyHead.next = node;
// 注:上面4行代码等价于下面1行(JS的语法糖)
// [node.prev, node.next, dummyHeadNext.prev, dummyHead.next] = [dummyHead, dummyHeadNext, node, node];
}
removeLRUItem() {
const {dummyTail = null, map = new Map()} = this,
tailNode = dummyTail.prev;
// 删除尾结点 并更新容量(即 curCapacity )信息
this.removeFromList(tailNode);
map.delete(tailNode.key);
this.curCapacity--;
}
}
四 资源分享 & 更多
1 历史文章 - 总览
2 博主简介
码农三少 ,一个致力于编写 极简、但齐全题解(算法) 的博主。
专注于 一题多解、结构化思维 ,欢迎一起刷穿 LeetCode ~