Pretty clean 92 ms C++ Solution


  • 6
    G
    class LRUCache {
    public:
    	int maxCap;
    	list<pair<int, int>> cache;
    	unordered_map<int, list<pair<int, int>>::iterator> keyLoc;
    
    	LRUCache(int capacity) {
    		maxCap = capacity;
    	}
    
    	void touch(list<pair<int, int>>::iterator &iter) {
    		cache.push_back(*iter);
    		keyLoc[iter->first] = --(cache.end());
    		cache.erase(iter);
    	}
    
    	int get(int key) {
    		int value = -1;
    
    		if (keyLoc.find(key) != keyLoc.end()) {
    			list<pair<int, int>>::iterator iter = keyLoc[key];
    			value = iter->second;
    			touch(iter);
    		}
    
    		return value;
    	}
    
    	void set(int key, int value) {
    		list<pair<int, int>>::iterator iter;
    
    		if (keyLoc.find(key) == keyLoc.end()) {
    			if ((int) keyLoc.size() == maxCap) {
    				iter = cache.begin();
    				keyLoc.erase(iter->first);
    				cache.erase(iter);
    			}
    
    			cache.push_front(make_pair(key, value));
    			iter = cache.begin();
    		} else {
    			iter = keyLoc[key];
    			iter->second = value;
    		}
    
    		touch(iter);
    	}
    };

Log in to reply
 

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