题解 | #设计LRU缓存结构#

首先是使用何种数据结构？

不考虑时间复杂度的话用栈会非常清晰，新的入栈，旧的从栈底去除，更新的从栈中拿到栈顶即可。

但如果要考虑取值的时间复杂试为O(1)的话，我们可以使用map来解决。同时考虑更新值也为O(1)的话，就不能使用栈了，更新值会导致其余值的移动，所以考虑使用链表。

这样的话数据结构就确定了，使用map+list的形式。

其次是如何实现？

• 首先是set添加元素：如果是新key,则创建新结点添加到链表尾部前方，并在map中注册（如果已达到容量需要从链表头部删除一个元素，并且从map中去除该key）；如果是map中已有的key, 则更新值后拿到尾部前方

• 其次是get访问元素：类似地，如果是新key,则返回-1；如果是map中已有的key,则拿到尾部前方

具体看代码：

struct node {
    int value;
    node* pre;
    node* suf;
    int key;
};

void deleteNode(node* mid) {
    mid->suf->pre = mid->pre;
    mid->pre->suf = mid->suf;
    delete mid;
    mid = nullptr;
}

void removeNode(node* mid) {
    mid->suf->pre = mid->pre;
    mid->pre->suf = mid->suf;
}

void addBeforeNode(node* mid, node* next) {
    mid->pre = next->pre;
    next->pre->suf = mid;
    mid->suf = next;
    next->pre = mid;
}

class Solution {
  private:
    map<int, node*> buffer_map;
    node* head;
    node* tail;
    int ele_n;
    int capacity;
  public:
    Solution(int capacity) : capacity(capacity) {
        // write code here
        ele_n = 0;
        // add the head
        head = new node();
        tail = new node();
        head->suf = tail;
        tail->pre = head;
    }

    void show() {
        node* tmp = head->suf;
        while (tmp->suf != nullptr) {
            cout << tmp->value << ",";
            tmp = tmp->suf;
        }
        cout << endl;
    }

    int get(int key) {
        // write code here
        if (buffer_map.count(key) == 0) { // 没有key信息
            return -1;
        } else { // 有key信息
            if (buffer_map[key] != tail->pre) { // 如果不在尾部
                // 取出节点
                removeNode(buffer_map[key]);
                // 拿到尾部
                addBeforeNode(buffer_map[key], tail);
            }
            return tail->pre->value;
        }

    }

    void set(int key, int value) {
        // write code here
        if (buffer_map.count(key) == 0) { // 新key
            if (ele_n == capacity) { // 已达到容量
                // 删除第一个节点
                buffer_map.erase(head->suf->key); // 从map中删除
                deleteNode(head->suf); // 从链表中删除
                ele_n--;
            }
            // 添加到链表尾部
            node* tmp = new node();
            tmp->key = key;
            tmp->value = value;
            addBeforeNode(tmp, tail);
            // 添加到map
            buffer_map[key] = tmp; // add key and node to map
            ele_n++;
        } else { // 已经存储的key
            if (buffer_map[key] != tail) { // 如果不在尾部
                // 更新值
                buffer_map[key]->value = value;
                // 取出节点
                removeNode(buffer_map[key]);
                // 拿到尾部
                addBeforeNode(buffer_map[key], tail);
            }
        }
    }
};