设计LRU缓存

思路：

链接转载于https://blog.nowcoder.net/n/b279555a5cfd48f28fec790d96b0a1b9

代码：

//双向链表的一个节点：包含该节点的值，对应map的索引，每个节点都有一个前驱指针和一个后驱指针
struct Node{ 
    int key;
    int val;
    Node* pre;
    Node* next;
    //初始化
    Node(int k, int v): key(k), val(v), pre(NULL), next(NULL){}; 
};

class Solution {
public:
    int size = 0;
    //双向链表头尾
    Node* head = NULL; 
    Node* tail = NULL;
    //哈希表记录key值
    unordered_map<int, Node*> mp;
    //读入操作和容量
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        vector<int> res;//用来记录get得到的值
        //构建初始化连接
        //链表剩余大小
        size = k; 
        head = new Node(0, 0);
        tail = new Node(0, 0);
        //将双向链表首尾相连
        head->next = tail;
        tail->pre = head;
        //操作数组为空，就直接返回
        if(operators.size() == 0) 
            return res;
        //遍历所有操作
        for(int i = 0; i < operators.size(); i++){ 
            auto op = operators[i];
            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){ 
        //没有见过这个key，新值加入
        if(mp.find(key) == mp.end()){ 
            Node* node = new Node(key, val);
            mp[key] = node;
            //超出大小，移除最后一个
            if(size <= 0) 
                removeLast();
            //大小还有剩余
            else 
                //大小减1
                size--; 
            //由于这个节点之前是不存在链表中的,所以要加到链表头
            insertFirst(node); 
        }
        //哈希表中已经有了，即链表里也已经有了
        else{  
            mp[key]->val = val;
            //访问过后，由于该节点原先已经存在在链表中，所以现在只需要将这个节点移到表头：在后面将这个节点去除后插入到表头
            moveToHead(mp[key]); 
        }
    }

    //获取数据函数
    int get(int key){ 
        //找不到返回-1
        int res = -1; 
        //哈希表中找到
        if(mp.find(key) != mp.end()){ 
            //获取
            res = mp[key]->val;
            //访问过后移到表头
            moveToHead(mp[key]); 
        }
        return res;
    }
    
    //移到表头函数
    void moveToHead(Node* node){ 
        //已经到了表头
        if(node->pre == head)  
            return;
        //将节点断开，取出来
        node->pre->next = node->next;
        node->next->pre = node->pre;
        //插入第一个前面
        insertFirst(node);
    }
    
    //将节点插入表头函数
    void insertFirst(Node* node){ 
        node->pre = head;
        node->next = head->next;
        head->next->pre = node;
        head->next = node;
    }
    
    //删去表尾函数，最近最少使用
    void removeLast(){ 
        //哈希表去掉key
        mp.erase(tail->pre->key);
        //断连该节点
        tail->pre->pre->next = tail; 
        tail->pre = tail->pre->pre;
    }
};