看题解太少了,小白也贴一个c++版本的。思路借鉴的@Kid201805122110924博主分享的题解思路。
开始初始化一个head节点与一个tail节点,方便以后插入节点和删除节点,中间放置操作的节点。
在这里插入图片描述

  1. [1,1,1] 当我们遇到第一个set方法的时候 就需要插入到head 和tail 之间,
    在这里插入图片描述

  2. [1,2,2] 这时我们需要将新节点插入到head与node(1,1)之间。
    图片说明

  3. [1,3,2] 添加到head后面;
    在这里插入图片描述

  4. [2,1] 发现已经有key=1对应的节点;则把Node(1,1)移动到head后面;
    在这里插入图片描述

  5. [1,4,4] 这时候发现节点的数量已经达到内存上限,则需要把最不常用的节点Node(2,2)删除,把新节点插入到head后面;
    在这里插入图片描述

  6. [2,2] 这时候查找节点发现没有,则返回-1;

code:

#include <unordered_map>

struct DListNode{
    int key, val;
    DListNode* pre;
    DListNode* next;
    DListNode(int k, int v): key(k), val(v), pre(nullptr), next(nullptr){};
};


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
        if(k < 1) return {};
        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){
            if(op[0] == 1) {
                set(op[1], op[2]);
            }
            else if(op[0] == 2){
                int value = get(op[1]);
                res.push_back(value);
            }
        }
        return res;
    }

    void set(int key, int val){
        if(mp.find(key) == mp.end()){ // hashmap 中没找到
            DListNode* node = new DListNode(key, val);
            mp[key] = node;
            if(this->size <= 0){
                removeLast();
            }
            else{
                this->size--;
            }
            insertFirst(node);
        }
        else{  // hashmap 中已经有了,也就是链表里也已经有了
            mp[key]->val = val;
            moveToHead(mp[key]);
        }
    }


    int get(int key){
        int ret = -1;
        if(mp.find(key) != mp.end()){
            ret = mp[key]->val;
            moveToHead(mp[key]);
        }
        return ret;
    }

    void moveToHead(DListNode* node){
        if(node->pre == this->head) return;
        node->pre->next = node->next;
        node->next->pre = node->pre;
        insertFirst(node);
    }


    void removeLast(){
        mp.erase(this->tail->pre->key);
        this->tail->pre->pre->next = this->tail; // remove the last node in dlist
        this->tail->pre = this->tail->pre->pre;
    }

    void insertFirst(DListNode* node){
        node->pre = this->head;
        node->next = this->head->next;
        this->head->next->pre = node;
        this->head->next = node;
    }

};