Leetocde146. LRU 缓存

【LeetCode 146. LRU 缓存【高频面试题】】 https://www.bilibili.com/video/BV1UL411c7qA/?share_source=copy_web&vd_source=afbacdc02063c57e7a2ef256a4db9d2a

class LRUCache {
public:
    struct Node{
        int k,v;
        Node* prev,*next;
        Node(int key,int val):k(key),v(val) , prev(nullptr) , next(nullptr)  {}
    }*h,*t;
    typedef Node* PNode;
    unordered_map<int,PNode> cache;
    int n , sz;//n是最大容量,sz是当前数量
    LRUCache(int capacity) {
        n = capacity;
        sz = 0;
        h = new Node(0,0) , t = new Node(0,0); 
        h->next = t;
        t->prev = h;
    }
    int get(int key) {
        if(!cache.count(key))
            return -1;
        PNode p = cache[key];
        moveToHead(p);
        return p->v;
    }
    void put(int key, int value) {
        if(!cache.count(key)){
            PNode p = new Node(key,value);
            cache[key] = p;
            add(p);
            ++sz;
            if(sz > n){//oversize
                PNode p = removeTail();//删除尾节点
                cache.erase(p->k);
                delete p;
                --sz;
            }
        }
        else{
            PNode p = cache[key];
            p->v = value;
            moveToHead(p);
        }
    }
    void add(PNode p){//
        p->prev = h;
        p->next = h->next;
        h->next->prev = p;
        h->next = p;
    }
    void remove(PNode p){
        p->prev->next = p->next;
        p->next->prev = p->prev;
    }
    void moveToHead(PNode p){
        remove(p);
        add(p);
    }
    PNode removeTail(){
        PNode p = t->prev;//方法体不能写成remove(pt->prev); return t->prev;
        remove(p);
        return p;
    }
};