本文共 1970 字，大约阅读时间需要 6 分钟。

struct DListNode{
       int key, value;    DListNode* pre;    DListNode* next;    DListNode():key(0),value(0),pre(nullptr),next(nullptr){
   }    DListNode(int _key, int _value):key(_key),value(_value),pre(nullptr),next(nullptr){
   }};class LRUCache {
   private:    unordered_map
   
     cache;    DListNode* head;    DListNode* tail;    int capacity, size;public:    LRUCache(int _capacity):capacity(_capacity),size(0) {
           head = new DListNode();        tail = new DListNode();        head->next = tail;        tail->pre = head;    }        int get(int key) {
           if(!cache.count(key))            return -1;        DListNode* temp = cache[key];        movetohead(temp);        return temp->value;    }        void put(int key, int value) {
           if(!cache.count(key)){
               DListNode* node = new DListNode();            node->key = key;            node->value = value;            addtohead(node);            cache[key] = node;            size++;            if(size>capacity){
                   DListNode* removed = removetail();                cache.erase(removed->key);                size--;            }        }else{
               DListNode* temp = cache[key];            temp->value = value;            movetohead(temp);        }    }    void addtohead(DListNode* node){
           head->next->pre = node;        node->next = head->next;        node->pre = head;        head->next = node;    }    void removenode(DListNode* node){
           node->pre->next = node->next;        node->next->pre = node->pre;    }    void movetohead(DListNode* node){
           removenode(node);        addtohead(node);    }    DListNode* removetail(){
           DListNode* node = tail->pre;        removenode(node);        return node;    }};/** * Your LRUCache object will be instantiated and called as such: * LRUCache* obj = new LRUCache(capacity); * int param_1 = obj->get(key); * obj->put(key,value); */
   

转载地址：http://hvyci.baihongyu.com/