C++ Simple code


  • 1
    J
    class LRUCache{
    private:
    unordered_map<int, list<pair<int, int>>::iterator> hmap;
    list<pair<int, int> >       q;
    int capacity;
    
    public:
    LRUCache(int capacity) {
    	this->capacity = capacity;
    }
    
    int get(int key) {
    	auto iter = hmap.find(key);
    	if (iter != hmap.end()) {			
    		q.splice(q.end(), q, iter->second);
    		return iter->second->second;
    	}
    
    	return -1;
    }
    
    void set(int key, int value) {
    	auto iter = hmap.find(key);
    	if (iter != hmap.end()) {
    		q.erase(iter->second);
    		hmap.erase(iter);
    	}
    	if (hmap.size() >= capacity) {
    		hmap.erase(hmap.find(q.begin()->first));
    		q.pop_front();
    	}
    
    	pair<int, int> t = { key, value }; q.push_back(t);
    	list <pair<int, int>>::iterator qiter = q.end(); qiter--;
    	hmap[t.first] = qiter;
    }
    };

Log in to reply
 

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