Lovely 30 line c++ 80ms solution


  • 4
    T
    class LRUCache{
        const int cap;
        unordered_map<int, list<pair<int, int> >::iterator> map;
        list<pair<int, int>> lst;
     public:
        LRUCache(int capacity):cap(capacity) {}
    
        int get(int key) {
            auto it = map.find(key);
            if(it == map.end()) return -1;
        
            lst.push_front(*it->second);
            lst.erase(it->second);
            it->second = lst.begin();
            return it->second->second;
        }
    
        void set(int key, int value) {
            auto it = map.find(key);
            if(it == map.end()){  // insert new
                while (map.size() >= cap) {
                    map.erase(lst.crbegin()->first);
                    lst.pop_back();
                }
            }else  // reset existed
                lst.erase(it->second);
        
            lst.push_front({key, value});
            map[key] = lst.begin();
        }
    };

  • 1
    F

    Concise Solution

    Your implementation with comments make it more clear

    
    class LRUCache{
    	const int cap;
    	//record the key and the corresponding position in the list 
    	//we use the map to record the current order of (key, value) in the cache 
    	unordered_map<int, list<pair<int, int>>::iterator> map;
    	//record the key and value of the data
    	list<pair<int, int>> lst;
     public:
        LRUCache(int capacity):cap(capacity) {}
    
        int get(int key) {
        	auto it = map.find(key);
        	if (it == map.end()) return -1;
        	//push the (key, value) to the top
        	lst.push_front(*it->second);
        	//erase the original occurrence
        	lst.erase(it->second);
        	it->second = lst.begin();
        	//return the fetched value 
        	return it->second->second;
        }
    
        void set(int key, int value) {
        	auto it = map.find(key);
        	//erase the original occurrence
        	if (it == map.end()) {
        		while (map.size() >= cap) {
        			//erase the tail elements in the lst and map
        			map.erase(lst.crbegin()->first);
        			lst.pop_back();
        		}
        	}
        	else {
        		lst.erase(it->second);
        	}
        	//add the new occurrence and update the map 
        	lst.push_front({key, value});
        	map[key] = lst.begin();
        }
    };

Log in to reply
 

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