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

知识点：双向哨兵链表

typedef struct Temp{
    struct Temp *prev;
    struct Temp *next;
    int key;
    int val;
}Temp;
map<int, Temp*> m;
Temp *head, *tail = NULL;
int maxk;


class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    void init(){
        head = new Temp();
        tail = new Temp();
        head->prev = tail;
        head->next = tail;
        tail->prev = head;
        tail->next = head;
    }
    void _del(Temp *node){
        assert(node != head);
        assert(node != tail);
        Temp *prev = node->prev;
        Temp *next = node->next;
        prev->next = next;
        next->prev = prev;
        
    }
    void del(){
        if(tail->prev != head){
            Temp *prev = tail->prev;
            m.erase(prev->key);
            _del(prev);
        }
    }
    Temp* create(int key, int val){
        Temp* node = new Temp();
        node->key = key;
        node->val = val;
        return node;
    }
    void insert(Temp *node, Temp *prev){
        Temp *oldnext = prev->next;
        node->prev = prev;
        node->next = oldnext;
        prev->next = node;
        oldnext->prev = node;
    }
    void move2head(Temp * node){
        if(node->prev != head){
            _del(node);
            insert(node, head);
        }
    }
    void set(int key, int val){
        if(m.find(key) == m.end()){
            if(m.size() >= maxk){
                del();
            }
            Temp *n = create(key, val);
            m[key] = n;
            insert(n, head);
        }
        else{
            Temp *n = m[key];
            n->val = val;
            move2head(n);
        }
    }
    int get(int key, int val){
        if(m.find(key) == m.end()){
            return -1;
        }
        int ret = m[key]->val;
        move2head(m[key]);
        return ret;
    }
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        // write code here
        maxk = k;
        init();
        vector<int> res;
        for(int i = 0; i < operators.size(); i++){
            vector<int> op = operators[i];
            int opt = op[0];
            int key = op[1];
            int val = op[2];
            if(opt == 1){
                set(key, val);
            }
            else{
                int ret = get(key, val);
                res.push_back(ret);
            }
            
        }
        return res;
        
    }
};