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

自己构建双链表，使用unordered_map容器

class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    // 构造双向链表和哈希表
    struct blist{ // 双向链表
        blist* next;
        blist* pre;
        int key;
        int val;
        blist(int k, int v) : key(k), val(v), next(NULL), pre(NULL) {}
    };
    blist* head = new blist(-1, -1);
    blist* tail = new blist(-1, -1);
    int length = 0;
    int capacity; // LRU容量
    unordered_map<int, blist*> mp; // 哈希表
    void set(int key, int value){
        if(mp.find(key) != mp.end()){
            auto q = mp[key];
            q->pre->next = q->next; // 先删去mp[key]节点
            q->next->pre = q->pre;
            delete q;
            // 防止新插入的节点的value值和前一个的value不相等，所以要重新创建一个新的节点
            auto node = new blist(key, value);
            // 讲解点插入到头结点后
            head->next->pre = node;
            node->next = head->next;
            node->pre = head;
            head->next = node;
        }else{
            auto node = new blist(key, value);
            mp[key] = node; // 建立映射
            length++; // LRU 容量增加
            // 插入新节点
            head->next->pre = node;
            node->next = head->next;
            node->pre = head;
            head->next = node;
            if(length > capacity){ // 更新LRU将tail节点前的节点删去
                auto q = tail->pre;
                q->pre->next = q->next;
                q->next->pre = q->pre;
                mp.erase(q->key);
                delete q;
            }
        }
    }
    int get(int key){
        if(mp.find(key) == mp.end()){ // 没有找到
            return -1;
        }else{
            auto node = mp[key];
            node->pre->next = node->next; // 先删去mp[key]节点
            node->next->pre = node->pre;
            // 将mp[key]节点插入头结点后
            head->next->pre = node;
            node->next = head->next;
            node->pre = head;
            head->next = node;
            return node->val;
        }
    }

    vector<int> LRU(vector<vector<int> >& operators, int k) {
        head->next = tail; // 将链表首位相连
        tail->next = head;
        capacity = k; 
        vector<int> res; // 输出
        for(int i = 0; i < operators.size(); i++){
            if(operators[i][0] == 1){
                int key = operators[i][1], value = operators[i][2];
                set(key, value);
            }else{
                int key = operators[i][1];
                int x = get(key);
                res.push_back(x);
            }
        }
        return res;
    }

};