146、LRU|146、LRU 缓存 | 算法(leetcode,附思维导图 + 全部解法)300题

零 标题:算法(leetcode,附思维导图 + 全部解法)300题之(146)LRU 缓存 一 题目描述 146、LRU|146、LRU 缓存 | 算法(leetcode,附思维导图 + 全部解法)300题
文章图片

146、LRU|146、LRU 缓存 | 算法(leetcode,附思维导图 + 全部解法)300题
文章图片

二 解法总览(思维导图) 146、LRU|146、LRU 缓存 | 算法(leetcode,附思维导图 + 全部解法)300题
文章图片

三 全部解法 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 历史文章 - 总览 146、LRU|146、LRU 缓存 | 算法(leetcode,附思维导图 + 全部解法)300题
文章图片

146、LRU|146、LRU 缓存 | 算法(leetcode,附思维导图 + 全部解法)300题
文章图片

2 博主简介 【146、LRU|146、LRU 缓存 | 算法(leetcode,附思维导图 + 全部解法)300题】码农三少 ,一个致力于编写 极简、但齐全题解(算法) 的博主。
专注于 一题多解、结构化思维 ,欢迎一起刷穿 LeetCode ~

    推荐阅读