题目描述

运用你所掌握的数据结构，设计和实现一个 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

算法

(双向链表 + 哈希表) $O(1)$

1. key-value 的增删改查显然需要用一个哈希表来实现，这道题困难地方在于删除时，如何查找需要删除的元素。
2. 我们使用一个双向链表来实现：初始时链表中有两个 dummy 结点，分别是 head 和 tail；新插入一个元素，将其插入到 tail 的前，然后在哈希表中记录下新元素的结点地址。
3. 遇到要删除的时候，删除 head 之后的那个结点，同时释放哈希表的内存。
4. 遇到 get 操作或者 set 操作时，通过哈希表找到这个结点的地址，然后将其取出，放到 tail 前，然后修改哈希表。

时间复杂度

• 哈希表的增删改查平均情况时间复杂度为 $O(1)$，双向链表的删除和插入结点的时间复杂度为 $O(1)$。
• 故总时间复杂度为 $O(1)$。

空间复杂度

• 哈希表最多占用 $O(capacity)$ 的空间，链表也最多占用 $O(capacity)$ 的空间。
• 故总空间复杂度为 $O(capacity)$。

C++ 代码

class Node {
public:
    int k, v;
    Node *prev, *nxt;

    Node (int k_, int v_) {
        k = k_; v = v_;
        prev = nxt = nullptr;
    }
};

class LRUCache {
public:
    int c, tot;
    Node *head, *tail;
    unordered_map<int, Node*> dic;

    LRUCache(int capacity) {
        tot = 0;
        c = capacity;

        head = new Node(-1, -1);
        tail = new Node(-1, -1);

        head->nxt = tail;
        tail->prev = head;
    }

    void remove(Node *node) {
        node->prev->nxt = node->nxt;
        node->nxt->prev = node->prev;
    }

    void insert_to_tail(Node *node) {
        node->nxt = tail;
        node->prev = tail->prev;

        tail->prev->nxt = node;
        tail->prev = node;
    }

    int get(int key) {
        if (dic.find(key) == dic.end())
            return -1;

        Node *node = dic[key];
        remove(node);
        insert_to_tail(node);

        return node->v;
    }

    void put(int key, int value) {
        if (dic.find(key) != dic.end()) {
            Node *node = dic[key];

            node->v = value;

            remove(node);
            insert_to_tail(node);
        } else {
            if (tot == c) {
                Node *node = head->nxt;
                dic.erase(node->k);

                remove(node);

                delete node;
                tot--;
            }

            Node *node = new Node(key, value);

            dic[key] = node;
            insert_to_tail(node);

            tot++;
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */