Sharing my 68ms C++ solution


  • 0
    T
    struct dListNode
    {
        int key;
        int val;
        dListNode *next;
        dListNode *prev;
        dListNode(int x, int y)
        {
            key = x;
            val = y;
            next = NULL;
            prev = NULL;
        }
    }; 
    // define the data structure for the node of doubly linked list
    
    class LRUCache{
    private:
        unordered_map<int, dListNode*> myMap; // search at constant time complexity
        dListNode *head; // latest
        dListNode* tail; // oldest
        int maximum;
        
        void updateToHead(dListNode *p)
        {
            if(p==head)
                return;
            else if(p==tail)
            {
                dListNode *temp = tail->prev;
                tail->prev = NULL;
                tail->next = head;
                head->prev = tail;
                head = tail;
                temp->next = NULL;
                tail = temp;
            }
            else
            {
                p->prev->next = p->next;
                p->next->prev = p->prev;
                p->prev = NULL;
                p->next = head;
                head->prev = p;
                head = p;
            }
        }
        
    public:
        LRUCache(int capacity) {
            maximum = capacity;
            head = NULL;
            tail = NULL;
        }
        
        int get(int key) {
            if(myMap.count(key)>0) // found
            {
                updateToHead(myMap[key]);
                return head->val;
            }
            else
                return -1;
        }
        
        void set(int key, int value) {
            if(myMap.count(key)>0)
            {
                updateToHead(myMap[key]);
                head->val = value;
            }
            
            else
            {
                if(myMap.size()==maximum)
                {
                    myMap.erase(tail->key);
                    dListNode *tailPrev = tail->prev;
                    delete tail;
                    tail = tailPrev;
                    if(tail)
                        tail->next = NULL;
                    else
                        head = NULL;
                }
                dListNode *newNode = new dListNode(key, value);
                newNode->prev = NULL;
                newNode->next = head;
                if(head)
                    head->prev = newNode;
                else
                    tail = newNode;
                head = newNode;
                myMap[key] = head;
            }
        }
    };

  • 0
    T
    This post is deleted!

Log in to reply
 

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