[LeetCode]LRU Cache

Map 加 Doubly Linkedlist 的实现策略，注意每一次 set 或者 get 之后要把相应的 node 移到头，然后注意处理 set 的时候，当前 cache 是空或者满了的情况，代码如下：

	struct Node
	{
	int val, key;
	Node* next, *prev;
	Node()
	{
	}
	Node(int k, int v)
	{
	key = k;
	val = v;
	next = nullptr;
	prev = nullptr;
	}
	};
	class LRUCache {
	public:
	LRUCache(int capacity) {
	m_cap = capacity;
	m_size = 0;
	m_head = nullptr;
	m_tail = nullptr;
	}
	int get(int key) {
	if(!m_cap)return -1;
	if(m_map.find(key) != m_map.end())
	{
	auto node = m_map[key];
	int res = node->val;
	moveToHead(node);
	return res;
	}
	return -1;
	}
	void put(int key, int value) {
	if(!m_cap)return;
	if(m_map.find(key) != m_map.end())
	{
	auto node = m_map[key];
	node->val = value;
	moveToHead(node);
	}
	else
	{
	auto node = new Node(key, value);
	m_map[key] = node;
	node->next = m_head;
	if(m_head)m_head->prev = node;
	m_head = node;
	if(!m_tail)m_tail = node;
	++m_size;
	if(m_size > m_cap)
	{
	int delKey = m_tail->key;
	m_tail = m_tail->prev;
	m_tail->next->prev = nullptr;
	m_tail->next = nullptr;
	--m_size;
	m_map.erase(delKey);
	}
	}
	}
	private:
	void moveToHead(Node* node)
	{
	if(node != m_head)
	{
	node->prev->next = node->next;
	if(node->next)node->next->prev = node->prev;
	if(node == m_tail)m_tail = node->prev;
	node->next = m_head;
	m_head->prev = node;
	node->prev = nullptr;
	m_head = node;
	}
	}
	int m_size, m_cap;
	Node* m_head, *m_tail;
	unordered_map<int, Node*> m_map;
	};
	/**
	* Your LRUCache object will be instantiated and called as such:
	* LRUCache obj = new LRUCache(capacity);
	* int param_1 = obj.get(key);
	* obj.put(key,value);
	*/

view raw LRU Cache.cpp hosted with ❤ by GitHub