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

    int key, val;
    DListNode* pre;
    DListNode* nex;
    DListNode(int key, int val):key(key), val(val), pre(NULL), nex(NULL){};
};

class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    int size = 0;
    DListNode* head;
    DListNode* tail;
    unordered_map<int, DListNode*> hash;
    vector<int> LRU(vector<vector<int> >& ops, int k) {
        // write code here
        this->size = k;
        this->head = new DListNode(0, 0);
        this->tail = new DListNode(0, 0);
        this->head->nex = this->tail;
        this->tail->pre = this->head;
        
        vector<int> res;
        if(ops.empty()) return res;  //进行判空校验
        for(auto op : ops){
            if(op[0] == 1){ //set操作
                set(op[1], op[2]);
            }else if(op[0] == 2){ //get操作
                res.push_back(get(op[1]));
            }
        }
        return res;
    }
    
    void set(int key, int val){
        if(hash.find(key) != hash.end()){
            //说明已经存在了key的节点，这时候只需要更新值即可
            hash[key]->val = val;
            move2Head(hash[key]);
        }else{
            //说明原先并无此节点，则进行创建
            DListNode* node = new DListNode(key, val);
            hash[key] = node;
            if(this->size <= 0){
                removeLast();
            }else this->size--;
            insertFirst(node);
        }
    }
    
    int get(int key){
        int ans = -1;
        if(hash.find(key) != hash.end()){
            ans = hash[key]->val;
            move2Head(hash[key]);
        }
        return ans;
    }
    
    void insertFirst(DListNode* node){
        node->pre = this->head;
        node->nex = this->head->nex;
        this->head->nex->pre = node;
        this->head->nex = node;
    }
    
    void move2Head(DListNode* node){
        if(node->pre == this->head) return;
        node->pre->nex = node->nex;
        node->nex->pre = node->pre;
        insertFirst(node);
    }
    
    void removeLast(){
        hash.erase(this->tail->pre->key);
        this->tail->pre->pre->nex = this->tail;
        this->tail->pre = this->tail->pre->pre;
    }
};