146. LRU Cache

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 <= 10^5
• 最多调用 2 * 10^5 次 get 和 put

1. 哈希表 + 双向链表

若使用哈希表, 无法表示最近最少使用的值.

若使用哈希表+单向链表, 那么删除节点时需要去寻找前一节点, 时间为O(n), 而双向链表寻找前一节点的时间为O(1).

哈希表的值, 存储在双向链表中. 每当进行put或get操作时, 将操作节点移动到表尾. 那么, 表头的节点一定时最近最少使用的节点.

put:

• 若缓存未满, 则插入链表尾部.
• 缓存已满, 删除头节点, 插入链表尾部.

get:

1. 获取节点值
2. 删除节点, 插入到表尾

type LRUCache struct {
    head *DoublyListNode
    tail *DoublyListNode
    cache map[int]*DoublyListNode
    Capacity int
}

type DoublyListNode struct {
    Key int
    Val int
    Prev *DoublyListNode
    Next *DoublyListNode
}

func Constructor(capacity int) LRUCache {
    head := &DoublyListNode{Key: -1, Val: -1}
    tail := &DoublyListNode{Key: -1, Val: -1}
    head.Next = tail
    tail.Prev = head

    return LRUCache{
        head: head,
        tail: tail,
        cache: map[int]*DoublyListNode{},
        Capacity: capacity,
    }
}


func (c *LRUCache) Get(key int) int {
    node, ok := c.cache[key]
    if !ok {
        return -1
    }

    c.moveToTail(node, node.Val)
    return node.Val 
}


func (c *LRUCache) Put(key int, value int)  {
    if node, ok := c.cache[key]; ok {
        c.moveToTail(node, value)
    } else {
        if len(c.cache) == c.Capacity {
            toBeDel := c.head.Next
            c.deleteNode(toBeDel)
            delete(c.cache, toBeDel.Key)
        }

        node := &DoublyListNode{Key: key, Val: value}
        c.insertToTail(node)
        c.cache[key] = node
    }
}

func (c *LRUCache) moveToTail(node *DoublyListNode, val int) {
    c.deleteNode(node)
    node.Val = val
    c.insertToTail(node)
}

func (c *LRUCache) deleteNode(node *DoublyListNode) {
    node.Prev.Next = node.Next
    node.Next.Prev = node.Prev
}

func (c *LRUCache) insertToTail(node *DoublyListNode) {
    c.tail.Prev.Next = node
    node.Prev = c.tail.Prev
    node.Next = c.tail
    c.tail.Prev = node
}

• head, tail: 为哨兵节点, 方便插入和删除