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

一切都在注释中

链接：https://www.nowcoder.com/questionTerminal/e3769a5f49894d49b871c09cadd13a61?toCommentId=9033479
来源：牛客网

struct LinkedListed{
    int val;
    int key;
    LinkedListed* pre;
    LinkedListed* next;
    LinkedListed (): key(0),val(0),pre(nullptr),next(nullptr){}
    LinkedListed (int _key,int _val): key(_key),val(_val),pre(nullptr),next(nullptr){}
};
class Solution {

private:
    int size;
    int capacity;
    LinkedListed *f_head;
    LinkedListed *f_tail;
    unordered_map<int,LinkedListed*> temp;


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->size = 0;
        this->capacity = k;
        f_head = new LinkedListed();
        f_tail = new LinkedListed();
        f_head->next = f_tail;
        f_tail->pre = f_head;
        vector<int> ans;

        if(operators.size() == 0 || k < 1) return ans;

        for(vector<int> nums : operators){
            if(nums[0] == 1){//调用set
                set(nums[1],nums[2]);
            }else if(nums[0] == 2){//调用get
               int A_nums = get(nums[1]);
               ans.push_back(A_nums);
            }
        }
        return ans;
    }

    //set方法
    //没有节点:1.没有超过长度限制,直接加2.有超过长度限制,加然后删除最后节点(要释放)
    //有节点:更新节点然后放到链表头

    void set(int key,int val){
        //先用哈西定位看有没有这各key
        if(temp.find(key) == temp.end()){ //代表没有这个key
            LinkedListed* newNode = new LinkedListed(key,val);
            temp[key] = newNode;
            addToHead(newNode);
            size++;
            if(size > capacity){ //代表节点数量超过限制(删除最尾节点并且哈希也要山)
                LinkedListed* delNode = delTailNode();
                temp.erase(delNode->key);
                delete(delNode);
                size--;
            }
        }else{ //代表有这个key,那么去更新然后放到头部
            //用哈希定位
            temp[key]->val = val;
            moveNodeToHead(temp[key]);
        }
    }

    //get方法(有key把节点拿到链表头,然后返回节点的val,没有就返回-1)
    int get(int key){
        if(temp.find(key) == temp.end()) return -1;
        LinkedListed* node = temp[key];
        moveNodeToHead(node);
        return node->val;
    }

    //插入头部的
    void addToHead(LinkedListed* node){
        node->next = f_head->next;
        node->pre = f_head;
        f_head->next->pre = node;
        f_head->next = node;
    }

    //移除节点的
    void removeNode(LinkedListed* node){
        node->next->pre = node->pre;
        node->pre->next = node->next;
    }

    //移动节点到头部
    void moveNodeToHead(LinkedListed* node){
        removeNode(node);
        addToHead(node);
    }

    //移除尾巴的节点
    LinkedListed* delTailNode(){
        LinkedListed* node = f_tail->pre;
        removeNode(node);
        return node;
    }
};