C++ solution by mapping key to pointer in 80ms


  • 0
    W

    It is the same idea of Hash + double linked list. However, I didn't use std::list. I build the hash from key to pointer. The memory cost maybe lower than previous solutions.

    struct Node {
        int key;
        int val;
        Node * pre;
        Node * next;
        Node():key(-1),val(-1),pre(NULL), next(NULL){}
        Node(int k, int v, Node * p = NULL, Node *n = NULL):key(k),val(v),pre(p),next(n){}
    };
    
    class LRUCache{
        private:
           int cap;
           unordered_map<int, Node *> cache;
           Node * head;
           Node * tail;
        
        public:
           LRUCache(int capacity){
               cap = capacity;
               head = tail = NULL;
           }
           
           void updateNode(Node * node){
               if( node == tail )
                   return;
               if( node == head ){
                   head = node->next;
               }else{
                   node->pre->next = node->next;
                   node->next->pre = node->pre;
               }
               tail->next = node;
               node->pre = tail;
               node->next = NULL;
               tail = node;
           }
           
           int get(int key){
               if( cache.find(key) != cache.end() ){
                   Node * targetNode = cache[key];
                   updateNode(targetNode);
                   return targetNode->val;
               }else
                   return -1;
           }
           
           int set(int key, int value){
               if( cache.find(key) != cache.end() ){
                   Node * targetNode = cache[key];
                   targetNode->val = value;
                   updateNode(targetNode);
               }else{
                   while( cap != 0 && cache.size() >= cap ){
                       Node * delNode = head;
                       head = head->next;
                       if( head == NULL ) tail = NULL;
                       cache.erase(delNode->key);
                       delete delNode;
                   }
                   if( cap > 0 ){
                       Node *newNode = new Node(key, value, NULL, NULL);
                       if(tail != NULL){
                           tail->next = newNode;
                           newNode->pre = tail;
                           tail = newNode;
                       }else{
                           head = tail = newNode;
                       }
                       cache[key] = newNode;
                    }
               }
           }
    };

Log in to reply
 

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