leetcode 146. LRU Cache

本是古典何须时尚 2022-07-26 06:30 162阅读 0赞

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: `get` and `set`.

`get(key)` - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.  
`set(key, value)` - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

class LRUCache{
    	struct Node
    	{
    		int val;
    		int key;
    		Node*pre, *nxt;
    		Node(int x) :val(x)
    		{
    			pre = NULL;
    			nxt = NULL;
    		}
    	};
    	int capa;
    	int cursize;
    	Node*head;
    	Node*tail;
    	unordered_map<int, Node*>keymap;
    public:
    	~LRUCache()
    	{
    		for (unordered_map<int, Node*>::iterator it = keymap.begin(); it != keymap.end(); it++)
    			delete it->second;
    	}
    	LRUCache(int capacity) {
    		capa = capacity;
    		head = NULL;
    		tail = NULL;
    		cursize = 0;
    	}
    
    	int get(int key) {
    		if (capa > 0)
    		{
    			unordered_map<int, Node*>::iterator it = keymap.find(key);
    			if (it == keymap.end())
    				return -1;
    			Node*pre = it->second->pre;
    			Node*nxt = it->second->nxt;
    			if (pre != NULL)
    			{
    				if (it->second == tail)
    					tail = pre;
    				pre->nxt = nxt;
    				if (nxt!=NULL)
    				nxt->pre = pre;
    				it->second->nxt = head;
    				head->pre = it->second;
    				it->second->pre = NULL;
    				head = it->second;
    			}
    			return it->second->val;
    		}
    		return -1;
    	}
    
    	void set(int key, int value) {
    		if (capa > 0)
    		{
    			unordered_map<int, Node*>::iterator it = keymap.find(key);
    			if (it == keymap.end())
    			{
    				if (cursize == capa)
    				{
    					keymap.erase(keymap.find(tail->key));
    					tail->key = key;
    					tail->val = value;
    					keymap[key] = tail;
    					if (head != tail)
    					{
    						Node*pre = tail->pre;
    						pre->nxt = NULL;
    						tail->nxt = head;
    						head->pre = tail;
    						head = tail;
    						head->pre = NULL;
    						tail = pre;
    					}
    				}
    				else
    				{
    					Node*n = new Node(value);
    					n->key = key;
    					if (head == NULL)
    					{
    						head = n;
    						tail = n;
    					}
    					else
    					{
    						n->nxt = head;
    						head->pre = n;
    						head = n;
    					}
    					keymap[key] = n;
    					cursize++;
    				}
    			}
    			else
    			{
    				Node*pre = it->second->pre;
    				Node*nxt = it->second->nxt;
    				if (pre != NULL)
    				{
    					if (it->second == tail)
    						tail = pre;
    					pre->nxt = nxt;
    					if (nxt != NULL)
    						nxt->pre = pre;
    					it->second->nxt = head;
    					head->pre = it->second;
    					it->second->pre = NULL;
    					head = it->second;
    				}
    				it->second->val = value;
    			}
    		}
    	}
    };