题目

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类：

  • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

  • void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。


    进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例

  1. 输入
  2. ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
  3. [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
  4. 输出
  5. [null, null, null, 1, null, -1, null, -1, 3, 4]
  7. 解释
  8. LRUCache lRUCache = new LRUCache(2);
  9. lRUCache.put(1, 1); // 缓存是 {1=1}
  10. lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
  11. lRUCache.get(1);    // 返回 1
  12. lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
  13. lRUCache.get(2);    // 返回 -1 (未找到)
  14. lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
  15. lRUCache.get(1);    // 返回 -1 (未找到)
  16. lRUCache.get(3);    // 返回 3
  17. lRUCache.get(4);    // 返回 4

实现

思路1 哈希表+双向链表

首先根据题目的get函数要求，我们可以建立一个哈希表以146. LRU缓存机制 - 图1的时间找到key对应的节点。
然后根据put的要求，我们需要对LRU进行添加和删除的操作，所以可以使用队列或者双向链表这样的数据结构来维护LRU里的节点。

  1. class DLinkNode:
  2.     def __init__(self, key=0, value=0):
  3.         self.key = key
  4.         self.value = value
  5.         self.prev = None
  6.         self.next = None
  8. class LRUCache:
  10.     def __init__(self, capacity: int):
  11.         self.capacity = capacity
  12.         self.hashmap = dict()
  13.         self.head = DLinkNode()
  14.         self.tail = DLinkNode()
  15.         self.head.next = self.tail
  16.         self.tail.prev = self.head
  17.         self.size = 0
  19.     def get(self, key: int) -> int:
  20.         if key not in self.hashmap:
  21.             return -1
  22.         # 如果key存在，则先通过dict定位，再将节点移到头部
  23.         node = self.hashmap[key]
  24.         self.removeNode(node)
  25.         self.addHead(node)
  26.         return node.value
  29.     def put(self, key: int, value: int) -> None:
  30.         if key not in self.hashmap:
  31.             # 创建一个新的节点加入哈希表和链表中
  32.             node = DLinkNode(key, value)
  33.             # 注意这里哈希表里存的是node
  34.             self.hashmap[key] = node
  35.             self.addHead(node)
  36.             self.size += 1
  37.             # 如果链表超度超过容量
  38.             if self.size > self.capacity:
  39.                 removed = self.tail.prev
  40.                 self.removeNode(removed)
  41.                 self.hashmap.pop(removed.key)
  42.                 self.size -= 1
  43.         else:
  44.             # 如果存在则修改value，并移到头部
  45.             node = self.hashmap[key]
  46.             node.value = value
  47.             self.removeNode(node)
  48.             self.addHead(node)
  50.     def removeNode(self, node):
  51.         node.prev.next = node.next
  52.         node.next.prev = node.prev
  55.     def addHead(self, node):       
  56.         node.next = self.head.next
  57.         node.prev = self.head
  58.         self.head.next.prev = node
  59.         self.head.next = node
  62. # Your LRUCache object will be instantiated and called as such:
  63. # obj = LRUCache(capacity)
  64. # param_1 = obj.get(key)
  65. # obj.put(key,value)

时间复杂度：对put和get操作都是
空间复杂度：146. LRU缓存机制 - 图2