146、LRU|146、LRU 缓存 | 算法(leetcode,附思维导图 + 全部解法)300题
零 标题:算法(leetcode,附思维导图 + 全部解法)300题之(146)LRU 缓存
一 题目描述
文章图片
文章图片
二 解法总览(思维导图)
文章图片
三 全部解法
1 方案1
1)代码:
// 方案1 “自己。哈希法”。
// 技巧:遇到 O(1) 的get、put操作,优先考虑 哈希表(JS里的Map数据结构)。
/**
* @param {number} capacity
*/
var LRUCache = function(capacity) {
this.capacity = capacity;
this.curCapacity = 0;
// 注:越是最近使用的key,就越往 map 的后面放!
this.map = new Map();
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
const {map} = this;
let resVal = -1;
// 边界1:get操作,若 已经有该key,
// 则 先删该key、接着把该key放到map的最后 —— 表示最近使用过该key!
if (map.has(key)) {
resVal = map.get(key);
map.delete(key);
map.set(key, resVal);
}return resVal;
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
const {capacity, curCapacity, map} = this;
// 边界2:put操作,若 已经有该key,
// 则 先删该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 = https://www.it610.com/article/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 = https://www.it610.com/article/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 博主简介 【146、LRU|146、LRU 缓存 | 算法(leetcode,附思维导图 + 全部解法)300题】码农三少 ,一个致力于编写 极简、但齐全题解(算法) 的博主。
专注于 一题多解、结构化思维 ,欢迎一起刷穿 LeetCode ~
推荐阅读
- nginx|Nginx网络服务
- TS使用
- 基础路径规划算法(Dijikstra、A*、D*)总结
- Java面试题总结(附答案)
- 读书名言
- 投稿|如祺、曹操出行花式求生
- mysql|Mysql触发器
- mysql|mysql 触发器 delete_MySQL触发器
- Spring事务源码解读
- 基于QT5的文件读取程序的实现