C++11 code 74ms - Hash table + List


  • 0
    M

    No exception safety in this solution (


  • 0
    O

    You don't need a third member function.

    class LRUCache {
    public:
        LRUCache(int capacity) {
            cap = capacity;
        }
        
        int get(int key) {
            if (h.find(key) == h.end())
                return -1;
            
            auto pos = h[key];
            auto res = *pos;
            lru_queue.erase(pos);
            lru_queue.push_front(res);
            h[key] = lru_queue.begin();
            return res.v;
        }
        
        void put(int key, int value) {
            if (get(key) != -1) {
                h[key]->v = value;
                return;   
            }
            
            lru_queue.emplace_front(key, value);
            h[key] = lru_queue.begin();
            
            while (lru_queue.size() > cap) {
                h.erase(lru_queue.back().k);
                lru_queue.pop_back();
            }
        }
        
    private:
        struct KVPair {
            int k, v;
            KVPair(int k, int v) : k(k), v(v) {}
        };
        
        list<KVPair> lru_queue;
        unordered_map<int, list<KVPair>::iterator> h;
        int cap;
    };
    

Log in to reply
 

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