146. LRU缓存机制

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

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

进阶:

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

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

python

class LRUCache(object): def __init__(self, capacity): self.capacity = capacity self._cache = [] self._cache_look_up = {} def get(self, key): if key in self._cache_look_up: self._cache.remove(key) self._cache.append(key) return self._cache_look_up[key] else: return -1 def put(self, key, value): if key in self._cache_look_up: self._cache_look_up[key] = value self._cache.remove(key) self._cache.append(key) return else: if len(self._cache) == self.capacity: del_key = self._cache[0] self._cache = self._cache[1:] del self._cache_look_up[del_key] self._cache.append(key) self._cache_look_up[key] = value

python O(1)

class LinkNode(object): def __init__(self, key, val, prev_node=None, next_node=None): self.key = key self.val = val self.prev = prev_node self.next = next_node class DoubleLinkList(object): def __init__(self, capacity): self.capacity = capacity self.size = 0 self.head = None self.tail = None def append(self, node): """ :param node: :return: append a node to the double link list last """ if self.size == self.capacity: raise ValueError("The double link list has been full.") self.size += 1 if self.head is None: self.head = self.tail = node return self.tail.next = node node.prev = self.tail self.tail = node def delete(self, node): """ :param node: :return node: delete a node in double link list. switch(node): 1.node == self.head 2.node == self.tail 3.node in the double link list middle """ if self.size == 0: raise ValueError("can not delete empty double link list") self.size -= 1 if node == self.head: if node.next: node.next.prev = None self.head = node.next elif node == self.tail: if node.prev: node.prev.next = None self.tail = node.prev else: node.prev.next = node.next node.next.prev = node.prev return node class LRUCache(object): def __init__(self, capacity): self.capacity = capacity self.cache_look_up = {} self.cache_list = DoubleLinkList(capacity) def get(self, key): if key not in self.cache_look_up: return -1 node = self.cache_look_up[key] self.cache_list.delete(node) self.cache_list.append(node) return node.val def put(self, key, value): if key in self.cache_look_up: node = self.cache_look_up[key] node.val = value self.cache_list.delete(node) self.cache_list.append(node) else: if self.capacity == self.cache_list.size: head_node = self.cache_list.delete(self.cache_list.head) del self.cache_look_up[head_node.key] new_node = LinkNode(key, value) self.cache_look_up[key] = new_node self.cache_list.append(new_node)

参考：https://blog.csdn.net/laughing2333/article/details/70231547