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

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

P粉934491362
P粉934491362原创
2022年06月18日 13:16:43662浏览

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



二 解法总览(思维导图)

三 全部解法
1 方案1
1)代码:

  1. // 则 先删该key、接着把该key放到map的最后 —— 表示最近使用过该key!
  2. if (map.has(key)) {
  3. map.delete(key);
  4. map.set(key, value);
  5. return;
  6. }
  7. // 边界3:put操作,若 当前已经放不下了(即 curCapacity >= capacity ),
  8. // 则 删除map的第一个key 且 将新key放到map的最后 —— 表示最近使用过该key!
  9. if (curCapacity >= capacity) {
  10. for (const [key, val] of map) {
  11. map.delete(key);
  12. break;
  13. }
  14. map.set(key, value);
  15. }
  16. // 边界4:put操作,若 当前放得下(即 curCapacity < capacity ),
  17. // 则 直接将新key放到map的最后 —— 表示最近使用过该key 且 this.curCapacity++ 。
  18. else {
  19. map.set(key, value);
  20. this.curCapacity++;
  21. }
  22. // 注:以上 5行 ,可以合并成如下 2行 (但为了可读性,可分拆为 if、else 2分支):
  23. // }
  24. // map.set(key, value);
  25. };

2 方案2
1)代码:

  1. // 方案2 “自己。哈希表 + 双向链表”。
  2. // 参考:
  3. // 1)https://leetcode.cn/problems/lru-cache/solution/146-lru-huan-cun-ji-zhi-by-chen-wei-f-tl1n/
  4. // 思路:
  5. // 1)重点实现 ListNode 和 LRUCache 2个类。
  6. // 2)get、put操作:
  7. // 根据当前情况进行 curCapacity、map、各种节点 的信息变更即可,详见代码的实现。
  8. //双向链表的单个节点
  9. class ListNode {
  10. constructor(key, value) {
  11. this.key = key;
  12. this.value = value;
  13. //指向后一个节点
  14. this.next = null;
  15. //指向前一个节点
  16. this.prev = null;
  17. }
  18. }
  19. class LRUCache {
  20. constructor(capacity) {
  21. this.capacity = capacity;
  22. this.curCapacity = 0;
  23. this.map = new Map();
  24. this.dummyHead = new ListNode();
  25. this.dummyTail = new ListNode();
  26. this.dummyHead.next = this.dummyTail;
  27. this.dummyTail.prev = this.dummyHead;
  28. }
  29. get(key) {
  30. const {map = new Map()} = this,
  31. node = map.get(key);
  32. // 没找到
  33. if (!node) {
  34. return - 1;
  35. }
  36. // 找到,将该节点挪到头部,并返回相应的值
  37. this.moveToHead(node);
  38. return node.value;
  39. }
  40. put(key, value) {
  41. const {map = new Map()} = this,
  42. node = map.get(key);
  43. if (!node) {
  44. // 不存在该节点,则进行节点的创建。
  45. const newNode = new ListNode(key, value);
  46. map.set(key, newNode);
  47. // 加入头结点(addToHead),而不是挪(moveToHead)
  48. this.addToHead(newNode);
  49. this.curCapacity++;
  50. // 边界:超容量了,得删除
  51. if (this.curCapacity > this.capacity) {
  52. this.removeLRUItem();
  53. }
  54. }
  55. else {
  56. // 存在该节点,更新其值 并 将该节点挪到头部
  57. node.value = value;
  58. this.moveToHead(node);
  59. }
  60. }
  61. moveToHead(node) {
  62. //从链表中删除该节点 并 将该节点添加至头结点
  63. this.removeFromList(node);
  64. this.addToHead(node);
  65. }
  66. // 节点的删除(本质:指针指向的变更)
  67. removeFromList(node) {
  68. let nodePre = node.prev,
  69. nodeNext = node.next;
  70. nodePre.next = nodeNext;
  71. nodeNext.prev = nodePre;
  72. }
  73. // 节点加入链表头部 的指针操作
  74. addToHead(node) {
  75. const {dummyHead = null} = this,
  76. dummyHeadNext = dummyHead.next;
  77. node.prev = dummyHead;
  78. node.next = dummyHeadNext;
  79. dummyHeadNext.prev = node;
  80. dummyHead.next = node;
  81. // 注:上面4行代码等价于下面1行(JS的语法糖)
  82. // [node.prev, node.next, dummyHeadNext.prev, dummyHead.next] = [dummyHead, dummyHeadNext, node, node];
  83. }
  84. removeLRUItem() {
  85. const {dummyTail = null, map = new Map()} = this,
  86. tailNode = dummyTail.prev;
  87. // 删除尾结点 并更新容量(即 curCapacity )信息
  88. this.removeFromList(tailNode);
  89. map.delete(tailNode.key);
  90. this.curCapacity--;
  91. }
  92. }

四 资源分享 & 更多
1 历史文章 - 总览

2 博主简介
码农三少 ,一个致力于编写 极简、但齐全题解(算法) 的博主。
专注于 一题多解、结构化思维 ,欢迎一起刷穿 LeetCode ~

声明:本文内容转载自脚本之家,由网友自发贡献,版权归原作者所有,如您发现涉嫌抄袭侵权,请联系admin@php.cn 核实处理。
全部评论
文明上网理性发言,请遵守新闻评论服务协议