LeetCode HOT100 - LRU 缓存

逐个分析需求

首先 get 的操作显然能够想到使用哈希表

而 put 的话，如果只是修改还是可以用哈希表去解决的

但是有一个逐出最久未使用的关键字，这就想到要使用队列了

如果用数组去实现这个队列的话每次删除将是 O(n) ，不符合 O(1) 的时间复杂度

修改 O(1) 的话想到使用链表

又因为修改的时候我们需要直接知道它的前一个节点和后一个节点，因此使用双向链表

此时，我们大致知道了这里的实现要使用链表和哈希表

现在想怎么组合，也就是哈希表维护的是什么信息

正常情况下就是 unordered_map<int, int>

但是这里如果存放的是 int，那么查询到之后我们要把对应的节点放到队列的末尾，那不就还要知道这个 int 对应的是哪个节点吗

所以哈希表映射的是 链表节点， 同时这样修改的时候利用它的前驱和后驱进行修改

因为我们时刻要注意链表的头和尾，所以需要额外维护链表的头和尾节点

class Node {
public:
    int key, value;
    Node *pre, *nxt;
    Node(int k = 0, int v = 0) : key(k), value(v), pre(nullptr), nxt(nullptr) {}
};

class LRUCache {
public:
    int cap;
    unordered_map<int, Node*> mp;
    Node *head, *tail;
    LRUCache(int cap) : cap(cap) {
        head = new Node();
        tail = new Node();
        head->nxt = tail;
        tail->pre = head;
    }
    void totail(int key) {
        auto node = mp[key];
        node->pre->nxt = node->nxt;
        node->nxt->pre = node->pre;
        node->pre = tail->pre;
        node->nxt = tail;
        tail->pre->nxt = node;
        tail->pre = node;
    }
    int get(int key) {
        if (mp.count(key)) {
            totail(key);
            return mp[key]->value;
        }
        return -1;
    }
    void put(int key, int value) {
        if (mp.count(key)) {
            mp[key]->value = value;
            totail(key);
        } else {
            if (mp.size() == cap) {
                auto del = head->nxt;
                mp.erase(del->key);
                head->nxt = del->nxt;
                del->nxt->pre = head;
                delete del;
            }
            auto tmp = new Node(key, value);
            mp[key] = tmp;
            tmp->pre = tail->pre;
            tmp->nxt = tail;
            tail->pre->nxt = tmp;
            tail->pre = tmp;
        }
    }
};