My 77ms C++ Solutions with custom list


  • 0
    A
    struct __node__ {
      int key;
      int val;
      __node__ *prev;
      __node__ *next;
    };
    
    class LRUCache:public unordered_map<int, __node__ *>{
        int capacity;
        __node__ * head;
        __node__ * end;
        void moveNodeToBegin(__node__ *);
        void pop_back();
    public:
        LRUCache(int capacity):unordered_map<int, __node__ *>(){
            this->capacity=capacity;
            // LRUkey= * new list<int> ();
        }
    	
        int get(int key);
    	
        void set(int key, int value) ;
    	
    };
    int LRUCache::get(int key) {
        auto r=find(key);
        if (r==unordered_map::end()) return -1;
    	
        moveNodeToBegin(r->second);
        return r->second->val;
    }
    
    void LRUCache::set(int key, int value) {
        if (capacity==0) return;
        
        if (size()==0) {
            auto * ins=new __node__{key,value};
            head=end=ins;
            insert( { key , ins } ) ;
            return;
        }
        auto r=find(key);
        if (r!=unordered_map::end()) {
            moveNodeToBegin(r->second);  //
            r->second->val=value;               //just change the value
            return;
        }
        if (size()==capacity) {
            auto end_key=end->key;
            pop_back();
            erase(end_key);
        }
        auto * ins=new __node__{key,value,NULL,head};
        head->prev=ins;
        head=ins;
        insert({key,ins});
        
    }
    void LRUCache::moveNodeToBegin(__node__ * node){
        if(head==node)return;
        if (end==node) {
            end=end->prev;
        }
        if (node->next) {
            node->next->prev=node->prev;
        }
        node->prev->next=node->next;
        node->next=head;
        head=head->prev=node;
        head->prev=NULL;
    }
    void LRUCache::pop_back(){
        if (end->prev) {
            end->prev->next=NULL;
            end=end->prev;
        }
        else{
            end=NULL;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.