题目

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

  • 获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
  • 写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

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

  1. LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
  2. cache.put(1, 1);
  3. cache.put(2, 2);
  4. cache.get(1);       // 返回  1
  5. cache.put(3, 3);    // 该操作会使得密钥 2 作废
  6. cache.get(2);       // 返回 -1 (未找到)
  7. cache.put(4, 4);    // 该操作会使得密钥 1 作废
  8. cache.get(1);       // 返回 -1 (未找到)
  9. cache.get(3);       // 返回  3
  10. cache.get(4);       // 返回  4

方案一（有序字典）

  1. from collections import OrderedDict
  3. class LRUCache:
  4.     def __init__(self, capacity: int):
  5.         self.capacity = capacity
  6.         self._m = OrderedDict()
  8.     def get(self, key: int) -> int:
  9.         if key not in self._m:
  10.             return -1
  12.         self._m.move_to_end(key)
  13.         return self._m[key]
  15.     def put(self, key: int, value: int) -> None:
  16.         if key in self:
  17.             self.move_to_end(key)
  18.         self[key] = value
  19.         if len(self) > self.capacity:
  20.             self.popitem(last = False)
  • 使用 python3 的 OrderedDict；
  • 此处用法与队列相反，即最新的元素在队列尾部

    方案二（双向链表+hash表）

  1. class DLinkedNode:
  2.     def __init__(self, key=None, val=None):
  3.         self.key = key
  4.         self.val = val
  5.         self.prev = None
  6.         self.next = None
  8. class DLinked:
  9.     def __init__(self):
  10.         # 使用虚拟头结点和尾节点，初始化双向链表
  11.         self.head, self.tail = DLinkedNode(), DLinkedNode()
  12.         self.head.next = self.tail
  13.         self.tail.prev = self.head
  15.     def add_node_by_val(self, key, val) -> 'DLinkedNode':
  16.         '''在双向链表头部添加一个节点'''
  17.         node = DLinkedNode(key, val)
  18.         self.add_node(node)
  19.         return node
  21.     def add_node(self, node):
  22.         node.prev = self.head
  23.         node.next = self.head.next
  25.         self.head.next.prev = node
  26.         self.head.next = node
  28.     def delete_node(self, node: 'DLinkedNode'):
  29.         '''删除一个节点'''
  30.         node.prev.next = node.next
  31.         node.next.prev = node.prev
  33.     def move_to_head(self, node: 'DLinkedNode'):
  34.         self.delete_node(node)
  35.         self.add_node(node)
  37.     def delete_tail(self) -> 'DLinkedNode':
  38.         '''删除尾节点'''
  39.         tail = self.tail.prev
  40.         self.delete_node(tail)
  41.         return tail
  44. class LRUCache:
  45.     def __init__(self, capacity: int):
  46.         self.capacity = capacity
  47.         self._cache = {} # value: node
  48.         self._count = 0
  49.         self.dLink = DLinked()
  51.     def get(self, key: int) -> int:
  52.         if key not in self._cache:
  53.             return -1
  55.         node = self._cache[key]
  56.         self.dLink.move_to_head(node)
  57.         return node.val
  59.     def put(self, key: int, value: int) -> None:
  60.         # 已经存在这个key则进行更新
  61.         if key in self._cache:
  62.             node = self._cache[key]
  63.             self.dLink.delete_node(node)
  64.             new_node = self.dLink.add_node_by_val(key, value)
  65.             self._cache[key] = new_node
  66.             return
  68.         # 不存在则新增
  69.         if self._count < self.capacity:
  70.             self._count += 1
  71.         else:
  72.             tail = self.dLink.delete_tail()
  73.             del self._cache[tail.key]
  74.         node = self.dLink.add_node_by_val(key, value)
  75.         self._cache[key] = node