C++_AC_LRU


  • 0

    Three similar O(1) design questions on Leetcode:
    Leetcode432. All O(1) Data Structure

    Leetcode146. LRU

    Leetcode460. LFU


    class LRUCache{
    int size;
    int n = 0;
    unordered_map<int, list<pair<int,int>>::iterator> mp;
    list<pair<int,int>> info;
    
    public:
    LRUCache(int capacity){
        size = capacity;
    }
    
    int get(int key) {
        if(mp.find(key) == mp.end()) return -1;
        auto value = mp[key];
        info.splice(info.begin(),info, value);
        return mp[key]->second;
    }
    
    void set(int key, int value) {
        if(size <= 0) return;
        if(mp.find(key) != mp.end()){
            auto itr = mp[key];
            itr->second = value;
            info.splice(info.begin(), info, itr);
            return;
        }else if(n == size){
            auto K = info.back().first;
            mp.erase(K);
            info.pop_back();
            n--;
        }
        n++;
        info.emplace_front(key,value);//Inserts a new element to the beginning of the container
        mp[key] = info.begin();
     }
     };

Log in to reply
 

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