####LeetCode 面试题 16.25. LRU 缓存
设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。
它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
示例:
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
使用单链表
class Node:
def __init__(self, key, val):
self.key = key
self.val = val
self.next = None
class LRUCache:
def __init__(self, capacity=10):
'''index存储key对应的Node的Prev信息；head存储实际的链表'''
self.index = {}
self.head = Node(-1, -1)
self.tail = self.head
self.capacity = capacity
def put(self, key, val):
if self.get(key) != -1:
self.index[key].next.val = val
return
node = Node(key, val)
self.index[node.key] = self.tail
self.moveToTail(node)
if self.size() > self.capacity:
self.evict()
def get(self, key):
if key not in self.index:
return -1
pre = self.index[key]
cur = pre.next
if cur != self.tail:
pre.next = cur.next
self.index[cur.next.key] = pre
self.index[cur.key] = self.tail
self.moveToTail(cur)
return cur.val
def moveToTail(self, node: Node):
node.next = None
self.tail.next = node
self.tail = self.tail.next
def evict(self):
head = self.head
del self.index[head.next.key]
self.index[head.next.next.key] = self.head
self.head.next = self.head.next.next
def size(self):
return len(self.index)
使用双链表
## Last Frequence Cache
class Node:
def __init__(self, k, v):
self.key = k
self.val = v
self.prev = None
self.next = None
class DoubleLinkList:
def __init__(self):
self._head = Node(-1, -1)
self._tail = Node(-1, -1)
self._head.next = self._tail
self._tail.prev = self._head
self.size = 0
def push(self, node):
node.prev = self._tail.prev
node.next = self._tail
node.prev.next = node
self._tail.prev = node
self.size += 1
def remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
self.size -= 1
def head(self):
return self._head.next
def __str__(self):
node = []
nxt = self._head.next
for _ in range(self.size):
node.append(str(nxt.val))
nxt = nxt.next
return '->'.join(node)
class LRUCache:
def __init__(self, capacity=10):
self.capacity = capacity
self.data = {}
self.cache = DoubleLinkList()
def put(self, key, val):
if key in self.data:
node = self.data[key]
node.val = val
self.moveToTail(node)
return node.val
if len(self.data) >= self.capacity:
self.remove()
node = Node(key, val)
self.data[key] = node
self.cache.push(node)
def get(self, key):
if key not in self.data:
return -1
node = self.data[key]
self.moveToTail(node)
return node.val
def moveToTail(self, node):
self.cache.remove(node)
self.cache.push(node)
def remove(self):
head = self.cache.head()
del self.data[head.key]
self.cache.remove(head)
return head