C++ 260ms O(1) Solution


  • 0
    Y
    class LRUCache{
    public:
        LRUCache(int capacity) {
            m_cap = capacity;
            m_head = NULL;
            m_tail = NULL;
            m_size = 0;
        }
        
        int get(int key) {
            unordered_map<int, pair*>::iterator itr = m_map.find(key);
            if(itr==m_map.end())
                return -1;
            pair* curr = itr->second;
            update(curr);
            return curr->val;
        }
        
        void set(int key, int value) {
            unordered_map<int, pair*>::iterator itr = m_map.find(key);
            if(itr!=m_map.end()) {
                itr->second->val = value;
                update(itr->second);
            } else {
                pair* newPair = new pair;
                newPair->key = key;
                newPair->val = value;
                newPair->prev = NULL;
                newPair->next = m_head;
                if(m_head==NULL) {
                    m_head = newPair;
                    m_tail = newPair;
                } else {
                    m_head->prev = newPair;
                    m_head = newPair;
                }
                m_map[key] = newPair;
                m_size++;
                
                if(m_cap<m_size) {
                    m_map.erase(m_tail->key);
                    m_tail = m_tail->prev;
                    delete m_tail->next;
                    m_tail->next = NULL;
                    m_size--;
                }
            }
        }
        
    private:
        typedef struct pair {
            int key;
            int val;
            struct pair* next;
            struct pair* prev;
        } pair;
        
        void update(pair* p) {
            if(p->prev==NULL) {
                //do nothing
            } else if(p->next==NULL) { //the least recent
                m_tail = m_tail->prev;
                m_tail->next = NULL;
                p->prev = NULL;
                p->next = m_head;
                m_head->prev = p;
                m_head = p;
            } else {
                p->prev->next = p->next;
                p->next->prev = p->prev;
                p->prev = NULL;
                p->next = m_head;
                m_head->prev = p;
                m_head = p;
            }        
        }
        
        pair* m_head;
        pair* m_tail;
        unordered_map<int, pair*> m_map;
        int m_size;
        int m_cap;
    };

Log in to reply
 

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