146. Lru 缓存

146. LRU 缓存 #

链接 #

146. LRU 缓存

题目 #

请你设计并实现一个满足  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 * 105 次 get 和 put

解答 #

from collections import OrderedDict
class LRUCache:
    NOT_FOUND = -1

    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if not key in self.cache:
            return LRUCache.NOT_FOUND

        self.cache.move_to_end(key)
        return self.cache.get(key)

    def put(self, key: int, value: int) -> None:
        self.cache[key] = value
        self.cache.move_to_end(key)
        if len(self.cache) > self.capacity:
            self.cache.popitem(last = False)

另一种实现方式：

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = self.next = None

class DLinkedList:
    def __init__(self):
        self.sentinel = Node(None, None)
        self.sentinel.next = self.sentinel.prev = self.sentinel
        self.size = 0
    
    def append(self, node):
        node.next = self.sentinel
        node.prev = self.sentinel.prev
        self.sentinel.prev.next = node
        self.sentinel.prev = node
        self.size += 1
    
    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1
    
    def pop(self):
        if self.size == 0:
            return
        node = self.sentinel.next
        self.remove(node)
        return node

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.keyTable = {}
        self.cache = DLinkedList()
    
    def _move_to_end(self, node):
        self.cache.remove(node)
        self.cache.append(node)
    
    def get(self, key):
        if key not in self.keyTable:
            return -1
        node = self.keyTable[key]
        self._move_to_end(node)
        return node.value
    
    def put(self, key, value):
        if self.capacity == 0:
            return
        
        if key in self.keyTable:
            node = self.keyTable[key]
            node.value = value
            self._move_to_end(node)
        else:
            if len(self.keyTable) >= self.capacity:
                delNode = self.cache.pop()
                del self.keyTable[delNode.key]
            
            newNode = Node(key, value)
            self.keyTable[key] = newNode
            self.cache.append(newNode)
Edit Edit this page