My C++ solution


  • 0
    P
    typedef list<int>::iterator ListIt;
    class LRUCache{
        unordered_map<int, int> cache;
        unordered_map<int, ListIt> keyToIt;
        list<int> LRUList;
        int capacity;
    public:
        LRUCache(int capacity) {
            this->capacity = capacity;
        }
        
        int get(int key) {
            unordered_map<int,int>::iterator it = cache.find(key);
            if (it != cache.end()) {
                refresh(key);
                return it->second;
            } 
            return -1;
        }
        
        void refresh(int key) {
            if (keyToIt.find(key) != keyToIt.end()) {
                ListIt pos = keyToIt.find(key)->second;
                LRUList.erase(pos);
            }
            LRUList.push_back(key);
            ListIt listIt = LRUList.end();
            keyToIt[key] = --listIt;
        }
        
        void set(int key, int value) {
            if (cache.find(key) != cache.end()) {
                cache[key] = value;
                refresh(key);
                return;
            }
            
            if (cache.size() == capacity) {
                int removed_key = LRUList.front();
                LRUList.pop_front();
                cache.erase(cache.find(removed_key));
                keyToIt.erase(keyToIt.find(removed_key));
            }
            cache[key] = value;
            refresh(key);
        }
    };

Log in to reply
 

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