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

用 map 和 链表来组织结构

struct node{
        int key, val;
        node* pre;
        node* next;
        node(int k, int v): key(k), val(v), pre(nullptr), next(nullptr){};
    };

class Solution {
private:
    unordered_map<int, node*> mp;
    int cnt = 0;
    vector<int> res;
    node* head;
    node* tail;
    int size;
    int cap;
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        // write code here
        head = new node(0, 0);
        tail = new node(0, 0);
        head->next = tail;
        tail->pre = head;
        size = 0;
        cap = k;
        for(vector<int> op : operators){
            if(op[0] == 1){
                set(op[1], op[2]);
            }
            if(op[0] == 2){
                int value = get(op[1]);
                res.push_back(value);
                
            }
        }
        return res;
        
    }
    int get(int key){
        if(!mp.count(key)){
            return -1;
        }
        node* tmp = mp[key];
        movetohead(tmp);
        return tmp->val;
    }
    void set(int key, int val){
        if(!mp.count(key)){
            node* tar = new node(key, val);
            mp[key] = tar;
            addtohead(tar);
            ++size;
            if(size > cap){
                node* remo = removetail();
                mp.erase(remo->key);
                delete remo;
                --size;
            }
        }else{
            node* tar = mp[key];
            tar->val = val;
            movetohead(tar);
        }
        
    }
    void movetohead(node* tmp){
        removenode(tmp);
        addtohead(tmp);
    }
    void removenode(node* tmp){
        tmp->pre->next = tmp->next;
        tmp->next->pre = tmp->pre;
    }
    void addtohead(node* tmp){
        tmp->next = head->next;
        tmp->pre = head;
        head->next->pre = tmp;
        head->next = tmp;
    }
    node* removetail(){
        node* tmp = tail->pre;
        removenode(tmp);
        return tmp;
    }
};