146. LRU Cache - CPP - Solution


  • 4
    Y
    //146. LRU Cache
    //https://leetcode.com/problems/lru-cache/
    //https://github.com/soulmachine/leetcode
    #include <iostream>
    #include <list>
    #include <unordered_map>
    using namespace std;
    class LRUCache {
    public:
    	LRUCache(const int& c): capacity(c) {}
    
    	int get(const int& key) {
    		int result(-1);
    		if (this->CacheHashMap.count(key)) {
    			result = this->CacheHashMap[key]->value;
    			this->CacheList.splice(this->CacheList.begin(), this->CacheList, this->CacheHashMap[key]);
    			this->CacheHashMap[key] = this->CacheList.begin();
    		}
    		return result;
    	}
    
    	void set(const int& key, const int& value) {
    		if (this->CacheHashMap.count(key)) {
    			this->CacheHashMap[key]->value = value;
    			this->CacheList.splice(this->CacheList.begin(), this->CacheList, this->CacheHashMap[key]);
    			this->CacheHashMap[key] = this->CacheList.begin();
    		}
    		else {
    			if (this->CacheList.size() >= this->capacity) {
    				this->CacheHashMap.erase(this->CacheList.back().key);
    				this->CacheList.pop_back();
    			}
    			this->CacheList.push_front(CacheNode(key, value));
    			this->CacheHashMap[key] = this->CacheList.begin();
    		}
    	}
    private:
    	struct CacheNode {
    		int key;
    		int value;
    		CacheNode(const int& k, const int& v): key(k), value(v) {}
    	};
    	list<CacheNode> CacheList;
    	unordered_map<int, list<CacheNode>::iterator> CacheHashMap;
    	int capacity;
    };
    int main(int argc, char** argv) {
    	LRUCache lrucache(10);
    	return 0;
    }

  • 0
    P
        this->CacheList.splice(this->CacheList.begin(), this->CacheList, this->CacheHashMap[key]);
    

    What does this do?


  • 0
    V

    very nice solution , neat and clear


Log in to reply
 

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