146. LRU 缓存

Difficulty
Medium
Tags
链表
URL
https://leetcode-cn.com/problems/lru-cache/
Star
  • 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

法 1 双向链表实现

思路
按照get, put要求，只需要一个hashmap即可满足。
但是由于需要移除最长时间没用的缓存，所以借助双向链表来存储缓存。每次将最近访问的移动到链表头部。这样很久没访问的自然就在链表尾部了。
Q：如何将链表 和 hashmap 连接在一起呢？
hashmap中 val 为节点，保证可以从hashmap中得到链表节点
链表中额外存储key，保证了可以从链表节点得到 hashmap的键值对
Q：为什么要用双向链表
删除节点的时候方便，不需要从头再访问
Q：为什么链表中要存储key, 删除超过容量的末尾节点时，需要同时删除hashmap中的键值对，此时需要从链表节点获取key
题解
class Node:
    def __init__(self, val, key=-1, next=None, prev=None):
        self.val = val
        self.key = key
        self.next = next
        self.prev = prev

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.head = Node(0)
        self.tail = Node(0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.hash_map = {}

    def get(self, key: int) -> int:
        if key not in self.hash_map:
            return -1
        res = self.hash_map[key].val
        # 将节点 断开
        cur_node = self.hash_map[key]
        cur_node.prev.next = cur_node.next
        cur_node.next.prev =cur_node.prev
        # 将节点移动到链表头部
        cur_node.next = self.head.next
        self.head.next = cur_node
        cur_node.next.prev = cur_node
        cur_node.prev = self.head
        
        return res
        

    def put(self, key: int, value: int) -> None:
        if key in self.hash_map:
            self.hash_map[key].val = value
            cur_node = self.hash_map[key]
            cur_node.prev.next = cur_node.next
            cur_node.next.prev = cur_node.prev
        else:
            cur_node = Node(value, key)
            self.hash_map[key] = cur_node

            # 删除多余的节点
            if len(self.hash_map) > self.capacity:
                delet_node = self.tail.prev
                delet_node.prev.next = self.tail
                self.tail.prev = delet_node.prev
                del self.hash_map[delet_node.key]

        # 将curnode移动到链表头部
        cur_node.next = self.head.next
        self.head.next = cur_node
        cur_node.next.prev = cur_node
        cur_node.prev = self.head

        



# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)