A concise solution with list(double directed linked list) and unordered_map (hash map)


  • 0
    S

    many thanks to @mzchen , his code is always concise and clean

    unordered_map<int, pair<int, list<int>::iterator> > data;
    list<int> keys;
    int capacity;
    
    LRUCache(int capacity) : capacity(capacity) {
        data.reserve(capacity); 
    }
    
    void refresh(list<int>::iterator &ref) {
        if (keys.begin() == ref) return;
        keys.emplace_front(*ref);
        keys.erase(ref);
        ref = keys.begin();
    }
    
    int get(int key) {
        if (data.find(key) == data.end()) return -1;
        auto &ref = data[key];
        refresh(ref.second);
        return ref.first;
    }
    
    void set(int key, int value) {
        if (data.find(key) != data.end()) {
            auto &ref = data[key];
            ref.first = value;
            refresh(ref.second);
            return;
        }
        
        if (capacity == data.size()) {
            data.erase(keys.back());
            keys.pop_back();
        }
        
        keys.emplace_front(key);
        data[key] = make_pair(value, keys.begin());
    }

Log in to reply
 

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