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

C++，双链表+hashmap，面向对象题解。插入、读取复杂度均为O(1)

struct  DLinkedList{
    int key;
    int value;
    DLinkedList *pre;
    DLinkedList *next;
};

class LRUCache{
    private:
        int MAX_;
        int cnt=0;
        DLinkedList  *head,*tail;
        unordered_map<int,DLinkedList*>  rem;
    public:
        LRUCache(int max_){
            this->MAX_=max_;
            head=new DLinkedList();
            tail=new DLinkedList();
            head->pre=nullptr;
            head->next=tail;
            tail->pre=head;
            tail->next=nullptr;
        }

        void  addHead(DLinkedList *ll){
            auto  nxt=head->next;
            head->next=ll;
            ll->pre=head;
            ll->next=nxt;
            nxt->pre=ll;
        }

        void remove(DLinkedList *ll){
            auto left=ll->pre;
            auto right=ll->next;
            left->next=right;
            right->pre=left;
        }

        DLinkedList* popTail(){
            auto  ll=tail->pre;
            remove(ll);
            return ll;
        }

        void refresh(DLinkedList *ll){
            remove(ll);
            addHead(ll);
        }

        void  set(int key,int val){
            if(rem.find(key)!=rem.end()){
                auto ll=rem[key];
                ll->value=val;
                refresh(ll);
            }else{
                auto  ll=new  DLinkedList();
                ll->key=key;
                ll->value=val;
                rem[key]=ll;
                addHead(ll);
                cnt++;
                if(cnt>MAX_){
                    auto ll=popTail();
                    rem.erase(ll->key);
                    cnt--;
                }
            }
        }

        int get(int key){
            if(rem.find(key)!=rem.end()){
                auto ll=rem[key];
                refresh(ll);
                return ll->value;
            }else{
                return -1;
            }
        }

};


class Solution {
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
        LRUCache  lru(k);
        vector<int> res;
        for(auto oper:operators){
            if(oper[0]==1){
                lru.set(oper[1], oper[2]);
            }else if(oper[0]==2){
                res.push_back(lru.get(oper[1]));
            }
        }
        return res;
    }
};