devbox
一键难忘520
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

LeetCode - 146 LRU缓存（Java & JS & Py & C & C++）

作者：一键难忘520 | 2024-06-25 10:31:14

赞

踩

LeetCode - 146 LRU缓存（Java & JS & Py & C & C++）

题目来源

146. LRU 缓存 - 力扣（LeetCode）

题目描述

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

​

示例

输入

["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

输出

[null, null, null, 1, null, -1, null, -1, 3, 4]

说明

LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 105
  • 最多调用 2 * 10^5 次 get 和 put

题目解析

LRU缓存表需要实现如下两个操作：

  • get(key)：
  1. 如果对应key存在，则返回key对应的val，并更新对应key为最近访问。
  2. 如果对应key不存在，则返回-1。
  • put(key, val)：
  1. 如果对应key存在，则更新key的val，并更新对应key为最近访问。
  2. 如果对应key不存在，则需要先检查缓存表是否满了：如果满了，则需要删除最久未使用的key，否则不做删除动作。
  3. 之后新增key-val，并更新key为最近访问。

LRU和LFU的区别：

当空间不足时，LRU算法优先删除最久未使用的key。而LFU算法是优先删除最少使用的key，如果有多个最少使用的key，则找出其中最久未使用的key删除。

LRU的实现原理：

LRU缓存结构可以基于哈希表map和双向链表link来实现。

  • 哈希表map的键即为本题的key，值则是Node(key, val)，即包装了本题key,val的节点对象。
  • 双向链表link的节点元素即为Node。

这里哈希表map的值列 和 双向链表的节点 是共享Node的。如下图所示：

初始时，LRU缓存结构如下

lru.put(1,1)

通过哈希表map的键列，我们可以快速判断key是否已存在于LRU缓存中。

由于map不存在key=1，因此当前put是新增操作，且由于map中记录键数量<capacity，即容量足够，因此无需执行逐出操作。

下面我需要创建节点 Node(key=1, val=1)，并构建如下关系：

  • map的键列插入key=1，并key=1的值列和 Node(key=1, val=1) 关联
  • 将 Node(key=1, val=1) 头插入到双向链表Link 中（离链表头head越近，即为最近使用，离链表尾tail越近，即为最久未使用）

lru.put(2,2)

由于map不存在key=2的键，因此是put是新增操作，检查容量足够。

因此创建 Node(key=2, val=2) 后，构建如下关系。

lru.get(1)

由于map存在key=1的键，因此可以根据map[key=1]找到对应的节点Node(key=1, val=1)，并获取Node.val返回。

另外，get操作会更新key=1为最近使用，因此我们需要将Node(key=1, val=1)暂时从Link中移除，然后头插到Link。

lru.put(3,3)

由于map不存在key=3的键，因此是put是新增操作，但是此时我们发现map中记录了两个键，分别为key=1,key=2，已经装满了capacity=2的LRU缓存表，因此put新增操作前需要先逐出最久未使用的key。


前面我们说明过，离Link链表头越近的节点，则为最近使用，离Link链表尾越近的节点，则为最久未使用。

因此 Link.tail.prev 节点即为最久未使用的节点，此时我们需要删除它：

  • Link中删除该节点
  • 根据节点的Node.key，找到map[Node.key]的键，并删除该键

删除最久未使用后，容量足够放下新节点Node(key=3, val=3)

以上即为LRU缓存的实现原理的图示。大家可以对照下面代码实现，继续想想后面的图示。

Java算法源码

  1. import java.util.HashMap;
  2.  
  3. class LRUCache {
  4.     static class Node {
  5.         int key;
  6.         int val;
  7.         Node prev;
  8.         Node next;
  9.  
  10.         public Node() {};
  11.         public Node(int key, int val) {
  12.             this.key = key;
  13.             this.val = val;
  14.         }
  15.     }
  16.  
  17.     static class Link {
  18.         Node head;
  19.         Node tail;
  20.  
  21.         public Link() {
  22.             this.head = new Node();
  23.             this.tail = new Node();
  24.             this.head.next = this.tail;
  25.             this.tail.prev = this.head;
  26.         }
  27.  
  28.         public void removeNode(Node node) {
  29.             node.prev.next = node.next;
  30.             node.next.prev = node.prev;
  31.             node.prev = null;
  32.             node.next = null;
  33.         }
  34.  
  35.         public void addFirst(Node node) {
  36.             node.next = this.head.next;
  37.             this.head.next.prev = node;
  38.             this.head.next = node;
  39.             node.prev = this.head;
  40.         }
  41.     }
  42.  
  43.     int capacity;
  44.     Link link;
  45.     HashMap<Integer, Node> map;
  46.  
  47.     public LRUCache(int capacity) {
  48.         this.capacity = capacity;
  49.         this.link = new Link();
  50.         this.map = new HashMap<>();
  51.     }
  52.  
  53.     public int get(int key) {
  54.         if (this.map.containsKey(key)) {
  55.             Node node = this.map.get(key);
  56.  
  57.             this.link.removeNode(node);
  58.             this.link.addFirst(node);
  59.  
  60.             return node.val;
  61.         } else {
  62.             return -1;
  63.         }
  64.     }
  65.  
  66.     public void put(int key, int value) {
  67.         if (this.map.containsKey(key)) {
  68.             Node node = this.map.get(key);
  69.             this.link.removeNode(node);
  70.             this.link.addFirst(node);
  71.             node.val = value;
  72.         } else {
  73.             if (this.map.size() == this.capacity) {
  74.                 Node removed = this.link.tail.prev;
  75.                 this.link.removeNode(removed);
  76.                 this.map.remove(removed.key);
  77.             }
  78.  
  79.             Node newNode = new Node(key, value);
  80.             this.link.addFirst(newNode);
  81.             this.map.put(key, newNode);
  82.         }
  83.     }
  84. }
  85.  
  86. //public class Main {
  87. //    public static void main(String[] args) {
  88. //        LRUCache lRUCache = new LRUCache(2);
  89. //        lRUCache.put(1, 1); // 缓存是 {1=1}
  90. //        lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
  91. //        System.out.println(lRUCache.get(1));    // 返回 1
  92. //        lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
  93. //        System.out.println(lRUCache.get(2));    // 返回 -1 (未找到)
  94. //        lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
  95. //        System.out.println(lRUCache.get(1));    // 返回 -1 (未找到)
  96. //        System.out.println(lRUCache.get(3));    // 返回 3
  97. //        System.out.println(lRUCache.get(4));    // 返回 4
  98. //    }
  99. //}

 

JS算法源码

  1. class Node {
  2.   constructor(key, val) {
  3.     this.key = key;
  4.     this.val = val;
  5.     this.next = null;
  6.     this.prev = null;
  7.   }
  8. }
  9.  
  10. class Link {
  11.   constructor() {
  12.     this.head = new Node();
  13.     this.tail = new Node();
  14.     this.head.next = this.tail;
  15.     this.tail.prev = this.head;
  16.   }
  17.  
  18.   removeNode(node) {
  19.     node.prev.next = node.next;
  20.     node.next.prev = node.prev;
  21.     node.prev = null;
  22.     node.next = null;
  23.   }
  24.  
  25.   addFirst(node) {
  26.     node.next = this.head.next;
  27.     this.head.next.prev = node;
  28.     this.head.next = node;
  29.     node.prev = this.head;
  30.   }
  31. }
  32.  
  33. /**
  34.  * @param {number} capacity
  35.  */
  36. var LRUCache = function (capacity) {
  37.   this.capacity = capacity;
  38.   this.map = new Map();
  39.   this.link = new Link();
  40. };
  41.  
  42. /**
  43.  * @param {number} key
  44.  * @return {number}
  45.  */
  46. LRUCache.prototype.get = function (key) {
  47.   if (this.map.has(key)) {
  48.     const node = this.map.get(key);
  49.     this.link.removeNode(node);
  50.     this.link.addFirst(node);
  51.     return node.val;
  52.   } else {
  53.     return -1;
  54.   }
  55. };
  56.  
  57. /**
  58.  * @param {number} key
  59.  * @param {number} value
  60.  * @return {void}
  61.  */
  62. LRUCache.prototype.put = function (key, value) {
  63.   if (this.map.has(key)) {
  64.     const node = this.map.get(key);
  65.     this.link.removeNode(node);
  66.     this.link.addFirst(node);
  67.     node.val = value;
  68.   } else {
  69.     if (this.map.size == this.capacity) {
  70.       const removed = this.link.tail.prev;
  71.       this.link.removeNode(removed);
  72.       this.map.delete(removed.key);
  73.     }
  74.  
  75.     const newNode = new Node(key, value);
  76.     this.link.addFirst(newNode);
  77.     this.map.set(key, newNode);
  78.   }
  79. };
  80.  
  81. // const lRUCache = new LRUCache(2);
  82. // lRUCache.put(1, 1); // 缓存是 {1=1}
  83. // lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
  84. // console.log(lRUCache.get(1)); // 返回 1
  85. // lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
  86. // console.log(lRUCache.get(2)); // 返回 -1 (未找到)
  87. // lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
  88. // console.log(lRUCache.get(1)); // 返回 -1 (未找到)
  89. // console.log(lRUCache.get(3)); // 返回 3
  90. // console.log(lRUCache.get(4)); // 返回 4

 

Py算法源码

  1. class Node:
  2.     def __init__(self, key, val):
  3.         self.key = key
  4.         self.val = val
  5.         self.prev = None
  6.         self.next = None
  7.  
  8.  
  9. class Link:
  10.     def __init__(self):
  11.         self.head = Node(-1, -1)
  12.         self.tail = Node(-1, -1)
  13.         self.head.next = self.tail
  14.         self.tail.prev = self.head
  15.  
  16.     def removeNode(self, node):
  17.         node.prev.next = node.next
  18.         node.next.prev = node.prev
  19.         node.prev = None
  20.         node.next = None
  21.  
  22.     def addFirst(self, node):
  23.         node.next = self.head.next
  24.         self.head.next.prev = node
  25.         self.head.next = node
  26.         node.prev = self.head
  27.  
  28.  
  29. class LRUCache(object):
  30.  
  31.     def __init__(self, capacity):
  32.         """
  33.         :type capacity: int
  34.         """
  35.         self.capacity = capacity
  36.         self.map = {}
  37.         self.link = Link()
  38.  
  39.     def get(self, key):
  40.         """
  41.         :type key: int
  42.         :rtype: int
  43.         """
  44.         if key in self.map:
  45.             node = self.map[key]
  46.             self.link.removeNode(node)
  47.             self.link.addFirst(node)
  48.             return node.val
  49.         else:
  50.             return -1
  51.  
  52.     def put(self, key, value):
  53.         """
  54.         :type key: int
  55.         :type value: int
  56.         :rtype: None
  57.         """
  58.         if key in self.map:
  59.             node = self.map[key]
  60.             self.link.removeNode(node)
  61.             self.link.addFirst(node)
  62.             node.val = value
  63.         else:
  64.             if len(self.map) == self.capacity:
  65.                 node = self.link.tail.prev
  66.                 self.link.removeNode(node)
  67.                 self.map.pop(node.key)
  68.  
  69.             node = Node(key, value)
  70.             self.link.addFirst(node)
  71.             self.map[key] = node
  72.  
  73.  
  74. # if __name__ == '__main__':
  75. #     lRUCache = LRUCache(2)
  76. #     lRUCache.put(1, 1)  # 缓存是 {1=1}
  77. #     lRUCache.put(2, 2)  # 缓存是 {1=1, 2=2}
  78. #     print(lRUCache.get(1))  # 返回1
  79. #     lRUCache.put(3, 3)  # 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
  80. #     print(lRUCache.get(2))  # 返回-1
  81. #     lRUCache.put(4, 4)  # 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
  82. #     print(lRUCache.get(1))  # 返回-1
  83. #     print(lRUCache.get(3))  # 返回3
  84. #     print(lRUCache.get(4))  # 返回4

C算法源码

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define MAX_SIZE 10000
  5.  
  6. typedef struct NODE {
  7.     int key;
  8.     int val;
  9.     struct NODE *prev;
  10.     struct NODE *next;
  11. } Node;
  12.  
  13. Node *new_Node(int key, int val) {
  14.     Node *node = (Node *) malloc(sizeof(Node));
  15.     node->key = key;
  16.     node->val = val;
  17.     node->prev = NULL;
  18.     node->next = NULL;
  19.     return node;
  20. }
  21.  
  22. typedef struct LINK {
  23.     Node *head;
  24.     Node *tail;
  25. } Link;
  26.  
  27. Link *new_Link() {
  28.     Link *link = (Link *) malloc(sizeof(Link));
  29.     link->head = new_Node(-1, -1);
  30.     link->tail = new_Node(-1, -1);
  31.     link->head->next = link->tail;
  32.     link->tail->prev = link->head;
  33.     return link;
  34. }
  35.  
  36. void removeNode(Node *node) {
  37.     node->prev->next = node->next;
  38.     node->next->prev = node->prev;
  39.     node->prev = NULL;
  40.     node->next = NULL;
  41. }
  42.  
  43. void addFirst(Link *link, Node *node) {
  44.     node->next = link->head->next;
  45.     link->head->next->prev = node;
  46.     link->head->next = node;
  47.     node->prev = link->head;
  48. }
  49.  
  50.  
  51. typedef struct {
  52.     int capacity;
  53.     Node *map[MAX_SIZE];
  54.     int map_size;
  55.     Link *link;
  56. } LRUCache;
  57.  
  58.  
  59. LRUCache *lRUCacheCreate(int capacity) {
  60.     LRUCache *lru = (LRUCache *) malloc(sizeof(LRUCache));
  61.     lru->capacity = capacity;
  62.     lru->link = new_Link();
  63.  
  64.     lru->map_size = 0;
  65.     for (int i = 0; i < MAX_SIZE; i++) {
  66.         lru->map[i] = NULL;
  67.     }
  68.  
  69.     return lru;
  70. }
  71.  
  72. int lRUCacheGet(LRUCache *lru, int key) {
  73.     if (lru->map[key] != NULL) {
  74.         Node *node = lru->map[key];
  75.         removeNode(node);
  76.         addFirst(lru->link, node);
  77.         return node->val;
  78.     } else {
  79.         return -1;
  80.     }
  81. }
  82.  
  83. void lRUCachePut(LRUCache *lru, int key, int value) {
  84.     if (lru->map[key] != NULL) {
  85.         Node *node = lru->map[key];
  86.         removeNode(node);
  87.         addFirst(lru->link, node);
  88.         node->val = value;
  89.     } else {
  90.         if (lru->map_size == lru->capacity) {
  91.             Node *removed = lru->link->tail->prev;
  92.             removeNode(removed);
  93.             lru->map[removed->key] = NULL;
  94.             lru->map_size--;
  95.         }
  96.  
  97.         Node *newNode = new_Node(key, value);
  98.         addFirst(lru->link, newNode);
  99.         lru->map[key] = newNode;
  100.         lru->map_size++;
  101.     }
  102. }
  103.  
  104. void lRUCacheFree(LRUCache *lru) {
  105.     Node *cur = lru->link->head;
  106.  
  107.     while (cur != NULL) {
  108.         Node *next = cur->next;
  109.         free(cur);
  110.         cur = next;
  111.     }
  112.  
  113.     free(lru);
  114. }
  115.  
  116. //int main() {
  117. //    LRUCache *lru = lRUCacheCreate(2);
  118. //    lRUCachePut(lru, 1, 1);
  119. //    lRUCachePut(lru, 2, 2);
  120. //    printf("%d\n", lRUCacheGet(lru, 1));
  121. //    lRUCachePut(lru, 3, 3);
  122. //    printf("%d\n", lRUCacheGet(lru, 2));
  123. //    lRUCachePut(lru, 4, 4);
  124. //    printf("%d\n", lRUCacheGet(lru, 1));
  125. //    printf("%d\n", lRUCacheGet(lru, 3));
  126. //    printf("%d\n", lRUCacheGet(lru, 4));
  127. //
  128. //    lRUCacheFree(lru);
  129. //
  130. //    return 0;
  131. //}

 

C++算法源码

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Node {
  5. public:
  6.     int key{-1};
  7.     int val{-1};
  8.     Node *prev{};
  9.     Node *next{};
  10.  
  11.     Node() = default;
  12.  
  13.     Node(int key, int val) : key(key), val(val) {}
  14. };
  15.  
  16. class Link {
  17. public:
  18.     Node *head;
  19.     Node *tail;
  20.  
  21.     Link() {
  22.         this->head = new Node();
  23.         this->tail = new Node();
  24.         this->head->next = this->tail;
  25.         this->tail->prev = this->head;
  26.     }
  27.  
  28.     static void removeNode(Node *node) {
  29.         node->next->prev = node->prev;
  30.         node->prev->next = node->next;
  31.         node->prev = nullptr;
  32.         node->next = nullptr;
  33.     }
  34.  
  35.     void addFirst(Node *node) const {
  36.         node->next = this->head->next;
  37.         this->head->next->prev = node;
  38.         this->head->next = node;
  39.         node->prev = this->head;
  40.     }
  41. };
  42.  
  43. class LRUCache {
  44. public:
  45.     int capacity;
  46.     map<int, Node *> map;
  47.     Link *link;
  48.  
  49.     explicit LRUCache(int capacity) {
  50.         this->capacity = capacity;
  51.         this->link = new Link();
  52.     }
  53.  
  54.     int get(int key) {
  55.         if (this->map.count(key) > 0) {
  56.             Node *node = this->map[key];
  57.             Link::removeNode(node);
  58.             this->link->addFirst(node);
  59.             return node->val;
  60.         } else {
  61.             return -1;
  62.         }
  63.     }
  64.  
  65.     void put(int key, int value) {
  66.         if (this->map.count(key) > 0) {
  67.             Node *node = this->map[key];
  68.             Link::removeNode(node);
  69.             this->link->addFirst(node);
  70.             node->val = value;
  71.         } else {
  72.             if (this->map.size() == this->capacity) {
  73.                 Node *removed = this->link->tail->prev;
  74.                 Link::removeNode(removed);
  75.                 this->map.erase(this->map.find(removed->key));
  76.             }
  77.  
  78.             Node *newNode = new Node(key, value);
  79.             this->link->addFirst(newNode);
  80.             this->map[key] = newNode;
  81.         }
  82.     }
  83. };
  84.  
  85.  
  86. //int main() {
  87. //    LRUCache lru(2);
  88. //    lru.put(1, 1);
  89. //    lru.put(2, 2);
  90. //    cout << lru.get(1) << endl;
  91. //    lru.put(3, 3);
  92. //    cout << lru.get(2) << endl;
  93. //    lru.put(4, 4);
  94. //    cout << lru.get(1) << endl;
  95. //    cout << lru.get(3) << endl;
  96. //    cout << lru.get(4) << endl;
  97. //
  98. //    return 0;
  99. //}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/一键难忘520/article/detail/755943
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号