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

使用的结构是hash表+双链表，重点是掌握hash表和双链表的构造以及this指针的运用。

struct DListNode{
    int key,val;//hash表
    DListNode *pre;//双链表
    DListNode *next;
    DListNode(int k,int v):key(k),val(v),pre(NULL),next(NULL){};
};

class Solution {
private:
    int size=0;
    DListNode *head;
    DListNode *tail;
    unordered_map<int,DListNode*> mp;

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
        //要学会this指针的运用！！
        if(k<1)
            return {};//最大容量小于1则返回空数组
        this->size=k;//链表最大容量
        this->head=new DListNode(0,0);
        this->tail=new DListNode(0,0);
        this->head->next=this->tail;
        this->tail->pre=this->head;
        if(operators.size()==0)
            return {};
        vector<int> res;
        for(vector<int> op:operators)
        {//op表示operators数组集的每一个数组
            if(op[0]==1)
                set(op[1], op[2]);//插入新结点
            else if(op[0]==2)
            {//返回其value
                int value=get(op[1]);
                res.push_back(value);
            }
        }
        return res;
    }

public:
    void set(int key,int val)
    {//将记录（key，value）插入链表
        DListNode* node=new DListNode(key,val);//要插入的新结点
        if(mp.count(key))
        {//原mp中已存在key，只需改变val值，并移到head后
            mp[key]->val=val;
            moveTohead(mp[key]);
        }
        else
        {//原mp中不存在，则先判断当前链表大小，若小于1则删除最后一个结点，若大于1则当前大小减1，再在head后插入新节点
            mp[key]=node;
            if(this->size<1)
                remove();
            else
                this->size--;
            addFront(node);
        }
    }

public:
    int get(int key)
    {//提取key值对应value，若不存在则返回-1，若存在则返回value并将所在结点提前至head后
        if(!mp.count(key))
            return -1;
        int val=mp[key]->val;//注意mp[key]表示该结点
        moveTohead(mp[key]);
        return val;
    }

public:
    void addFront(DListNode* node)
    {//在链表头部添加结点node
        node->pre=this->head;
        node->next=this->head->next;//确定node的前驱后驱分别指向
        this->head->next->pre=node;
        this->head->next=node;//确定node的两个被指向
    }

public:
    void remove()
    {//删除链表最后一个结点
        mp.erase(this->tail->pre->key);//清除最后一个结点的key值
        this->tail->pre->pre->next=this->tail;//清除最后一个结点的前后连接关系
        this->tail->pre=this->tail->pre->pre;//并建立tail与倒数第二个结点的关系
    }

public:
    void moveTohead(DListNode* node)
    {//将结点移到头部
        if(node->pre==this->head) 
            return;//node在head后面即退出
        node->pre->next=node->next;//node前驱结点与node后驱（即tail）建立连接
        node->next->pre=node->pre;
        addFront(node);//在head后插入node，作为第一个结点
    }

};