My Accepted C++ solution in 328ms


  • 0
    V
    #ifndef LRU_CACHE_H
    #define LRU_CACHE_H
    
    #include <algorithm>
    #include <map>
    #include <deque>
    
    /************************************************************************/
    /* 
    	 
    	This cache was implemented with a hash_map and a deque;                       
    */
    /************************************************************************/
    
    // A list is NOT enough to implement the "LRU" feature
    // So we DO need other attribute in this struct like 
    // the KeyNode pointer
    struct KeyNode;
    struct ValueNode {
    	int value;
    	ValueNode *prev;
    	ValueNode *next;
    	KeyNode *key_node;
    
    	ValueNode(int _v, KeyNode *_k, ValueNode *_p = NULL, ValueNode *_n = NULL) : 
    		value(_v), key_node(_k), prev(_p), next(_n) { }
    };
    
    // We use hash_map to store the key
    struct KeyNode {
    	int key;
    	ValueNode *value_node;
    
    	KeyNode(int _k, ValueNode *_v = NULL) : key(_k), value_node(_v) { }
    };
    
    // Double list implementation
    class LRUStack {
    public:
    	LRUStack() : size(0), first(NULL), last(new ValueNode(0, NULL)) { }
    
    	void push(ValueNode *new_node)
    	{
    		// Size increment
    		++size;
    
    		if (this->first == NULL)
    		{
    			this->first = new_node;
    			this->first->prev = NULL;
    			this->first->next = this->last;
    			this->last->prev = this->first;
    
    			return;
    		}
    
    		// Change the original first node
    		this->first->prev = new_node;
    
    		// Change the new node
    		new_node->next = this->first;
    		new_node->prev = NULL;
    
    		// Set current first to new node
    		this->first = new_node;
    	}
    	
    	ValueNode *pop()
    	{
    		if (size != 0) --size;
    
    		// Pop the last out
    		ValueNode* result = this->last->prev;
    
    		if (result == NULL) return result;
    
    		this->last->prev = result->prev;
    		if (result->prev != NULL) 
    			result->prev->next = this->last;
    		else 
    			first = NULL;
    
    		result->prev = NULL;
    		result->next = NULL;
    
    		return result;
    	}
    
    	// Return the size of this stack
    	inline int cap() {
    		return size;
    	}
    
    	// Special function for LRU
    	void use(ValueNode *node)
    	{
    		if (node == first) return;
    
    		// Erase the node from list
    		if (node->prev != NULL)
    			node->prev->next = node->next;
    		if (node->next != NULL)
    			node->next->prev = node->prev;
    
    		// Put this node in the top
    		node->next	= this->first;
    		node->prev	= NULL;
    		this->first->prev = node;
    		this->first = node;
    	}
    
    private:
    	int size;
    	ValueNode *first;
    	ValueNode *last;
    };
    
    class LRUCache{
    public:
    	LRUCache(int capacity) : key_hash_map(), _capacity(capacity) { }
    
    	// Get the value from the hash_map which store the key and the pointer to value
    	// O(1)
    	int get(int key) {
    		std::map<int, KeyNode *>::iterator iter = this->key_hash_map.find(key);
    
    		// If we didn't find the key, we would get pointer to the end of our hash_map
    		if (iter == this->key_hash_map.end()) return -1;
    		else 
    		{
    			this->value_stack.use(iter->second->value_node);
    			return iter->second->value_node->value;
    		}
    	}
    
    	// We add a new value with new key into the cache 
    	// O(1)
    	void set(int key, int value) {
    		// Firstly, find the key in hash_map
    		std::map<int, KeyNode *>::iterator iter = this->key_hash_map.find(key);
    
    		// If we find the key in hash_map successfully
    		if (iter != this->key_hash_map.end())
    		{
    			iter->second->value_node->value = value;
    			value_stack.use(iter->second->value_node);
    			return;
    		}
    
    		// If we didn't find the key
    		KeyNode *k_node = new KeyNode(key);
    		ValueNode *v_node = new ValueNode(value, k_node);
    		k_node->value_node = v_node;
    
    		if (value_stack.cap() == _capacity)
    		{
    			// Remove the node with the lowest priority
    			ValueNode *node_to_remove = value_stack.pop();
    			if (node_to_remove == NULL) return;
    			key_hash_map.erase(node_to_remove->key_node->key);
    		}
    
    		key_hash_map.insert(std::pair<int, KeyNode *>(key, k_node));
    		value_stack.push(v_node);
    	}
    
    private:
    	std::map<int, KeyNode *>		key_hash_map;
    	LRUStack						value_stack;
    	const int						_capacity;
    };
    
    #endif // LRU_CACHE_H

  • 0
    S

    Thanks for high quality sharing. I removed the Chinese part. Discuss is English Only.


Log in to reply
 

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