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

struct dlistnode
{
    int key,val;
    dlistnode* prev;
    dlistnode* next;
    dlistnode():key(0),val(0),prev(nullptr),next(nullptr){};
    dlistnode(int _key,int _val):key(_key),val(_val),prev(nullptr),next(nullptr){};
    dlistnode(int _key,int _val,dlistnode* _prev,dlistnode* _next):key(_key),val(_val),prev(_prev),next(_next){};
};

class Solution{
public:
    int size;
    int capacity;
    unordered_map<int,dlistnode*> mp;
    dlistnode* first;
    dlistnode* last;
    Solution(int _capacity):size(0),capacity(_capacity){
        first = new dlistnode();//注意初始化，不然报段错误
        last = new dlistnode();
        first->next = last;
        last->prev = first;
    }

    int get(int key){
        if(mp.count(key)) {
            movehead(mp[key]);
            return mp[key]->val;
        }
        else return -1;
    }

    void set(int key,int val){
        if(mp.count(key)){
            movehead(mp[key]);
            mp[key]->val = val;
        }
        else{
            size++;
            if(size>capacity){
                dlistnode* ans = deletenode();
                if(mp.count(ans->key)){
                    mp.erase(ans->key);
                    delete ans;
                    size--;
                }
                dlistnode* tmp = new dlistnode(key,val);
                mp[key] = tmp;
                addhead(tmp);
            }
            else{
                dlistnode* tmp = new dlistnode(key,val);
                mp[key] = tmp;
                addhead(tmp);
            }
        }
    }
    void movehead(dlistnode* node){
        remove(node);
        addhead(node);
    }
    void addhead(dlistnode* node){
        node->prev= first;
        node->next = first->next;
        first->next->prev = node;
        first->next = node;
    }
    void remove(dlistnode* node){
        node->next->prev=node->prev;
        node->prev->next = node->next;
    }
    dlistnode* deletenode(){
        dlistnode* tmp = last->prev;
        remove(tmp);
        return tmp;
    }
};