O(1) c++ solution in 252ms


  • 0
    Q
    class LRUCache{
        struct NODE{
            int key;
            int val;
            NODE* pre;
            NODE* next;
            NODE(int key,int value):key(key),val(value),pre(NULL),next(NULL){}
            NODE():val(0),pre(NULL),next(NULL){}
        };
    private:
         unordered_map<int,NODE*> m_mp;
         int m_cap;
         int m_size;
         NODE* m_pHead;
         NODE* m_pTail;
    
        void putToHead(NODE* pNode)
        {
            pNode->pre=m_pHead;
            pNode->next=m_pHead->next;
            m_pHead->next->pre=pNode;
            m_pHead->next=pNode;
        }
    public:
        LRUCache(int capacity) {
            m_cap=capacity;
            m_size=0;
            m_mp.clear();
            m_pHead=new NODE;
            m_pTail=new NODE;
            m_pHead->next=m_pTail;
            m_pTail->pre=m_pHead;
            
        }
        ~LRUCache() {
            //m_cap=capacity;
            m_size=0;
            m_mp.clear();
            delete m_pHead;
            delete m_pTail;
        }
        int get(int key) {
            unordered_map<int,NODE*>::iterator iMp=m_mp.find(key);
            if(iMp==m_mp.end())
               return -1;
            else
            {
               NODE* pCur=iMp->second;
               NODE* pPre=pCur->pre;
               NODE* pNext=pCur->next;
               pPre->next=pNext;
               pNext->pre=pPre;
               putToHead(pCur);
               return pCur->val;
            }
        }
        
        void set(int key, int value) {
            unordered_map<int,NODE*>::iterator iMp=m_mp.find(key);
            if(iMp==m_mp.end())
            {
                NODE* p=new NODE(key,value);
                putToHead(p);
                m_mp[key]=p;
                m_size++;
            }
            else
            {
                NODE* p=iMp->second;
                p->val=value;
                NODE* pPre=p->pre;
                NODE* pNext=p->next;
                pPre->next=pNext;
                pNext->pre=pPre;
                putToHead(p);
            }
            if(m_size>m_cap)
            {
                NODE* pCur=m_pTail->pre;
                NODE* pPre=pCur->pre;
                pPre->next=m_pTail;
                m_pTail->pre=pPre;
                m_mp.erase(m_mp.find(pCur->key));
                delete pCur;
                m_size--;
            }
        }
    };

Log in to reply
 

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