146. LRU 缓存

请你设计并实现一个满足??LRU (最近最少使用) 缓存?约束的数据结构。

实现?LRUCache?类：

• LRUCache(int capacity)?以?正整数?作为容量?capacity?初始化 LRU 缓存
• int get(int key)?如果关键字?key?存在于缓存中，则返回关键字的值，否则返回?-1?。
• void put(int key, int value)?如果关键字?key?已经存在，则变更其数据值?value?；如果不存在，则向缓存中插入该组?key-value?。如果插入操作导致关键字数量超过?capacity?，则应该?逐出?最久未使用的关键字。

函数?get?和?put?必须以?O(1)?的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 105
• 最多调用?2 * 105?次?get?和?put

class Node
{
public:
?? ?int value;
?? ?Node*pre;
?? ?Node*next;

?? ?Node(int v)
?? ?{
?? ??? ?pre = nullptr;
?? ??? ?next = nullptr;
?? ??? ?value = v;
?? ?}
};

class LRUCache {
public:
?? ?LRUCache(int capacity) {

?? ??? ?size = capacity;
?? ?}
private:
?? ?map<int, int>m;
?? ?int size;
?? ?map<int, Node*>m_l;
?? ?Node*cur = nullptr;
?? ?Node*head = nullptr;
?? ?int curSize = 0;
public:
?? ?Node* insertNode(int key)
?? ?{
?? ??? ?Node* node = new Node(key);
?? ??? ?if (cur == NULL)
?? ??? ?{
?? ??? ??? ?head = node;
?? ??? ??? ?cur = node;
?? ??? ??? ?curSize++;
?? ??? ??? ?return node;
?? ??? ?}
?? ??? ?cur->next = node;
?? ??? ?node->pre = cur;
?? ??? ?cur = cur->next;
?? ??? ?curSize++;
?? ??? ?return node;
?? ?}

?? ?void deleteNode(Node*node)
?? ?{
?? ??? ?if (nullptr != node->pre && nullptr != node->next)
?? ??? ?{
?? ??? ??? ?node->pre->next = node->next;
?? ??? ??? ?node->next->pre = node->pre;
?? ??? ??? ?delete node;
?? ??? ??? ?node = nullptr;
?? ??? ??? ?curSize--;
?? ??? ??? ?return;
?? ??? ?}
?? ??? ?if (nullptr == node->pre && nullptr == node->next)
?? ??? ?{
?? ??? ??? ?delete node;
?? ??? ??? ?node = nullptr;
?? ??? ??? ?cur = nullptr;
?? ??? ??? ?curSize--;
?? ??? ??? ?return;
?? ??? ?}
?? ??? ?//delete head
?? ??? ?if (nullptr == node->pre)
?? ??? ?{
?? ??? ??? ?head = node->next;
?? ??? ??? ?node->next->pre = nullptr;
?? ??? ??? ?delete node;
?? ??? ??? ?node = nullptr;
?? ??? ??? ?curSize--;
?? ??? ??? ?return;
?? ??? ?}
?? ??? ?//delete tail?
?? ??? ?if (nullptr == node->next)
?? ??? ?{
?? ??? ??? ?node->pre->next = nullptr;
?? ??? ??? ?cur = node->pre;
?? ??? ??? ?delete node;
?? ??? ??? ?node = nullptr;
?? ??? ??? ?curSize--;
?? ??? ??? ?return;
?? ??? ?}
?? ?}

?? ?//delete head
?? ?void deleteHead()
?? ?{
?? ??? ?if (nullptr == head)
?? ??? ?{
?? ??? ??? ?return;
?? ??? ?}
?? ??? ?if (nullptr == head->next)
?? ??? ?{
?? ??? ??? ?curSize--;
?? ??? ??? ?delete head;
?? ??? ??? ?head = nullptr;
?? ??? ??? ?cur = nullptr;
?? ??? ??? ?return;
?? ??? ?}
?? ??? ?curSize--;
?? ??? ?Node*tmp = head->next;
?? ??? ?delete head;
?? ??? ?tmp->pre = nullptr;
?? ??? ?head = tmp;
?? ?}

public:
?? ?int get(int key) {
?? ??? ?if (m.count(key))
?? ??? ?{
?? ??? ??? ?Node *node = m_l[key];
?? ??? ??? ?deleteNode(node);
?? ??? ??? ?auto pos1 = m_l.find(key);
?? ??? ??? ?m_l.erase(pos1);
?? ??? ??? ?m_l[key] = insertNode(key);
?? ??? ??? ?return m[key];
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?return -1;
?? ??? ?}
?? ?}

?? ?void put(int key, int value) {
?? ??? ?if (m.count(key))
?? ??? ?{
?? ??? ??? ?m[key] = value;
?? ??? ??? ?Node *node = m_l[key];
?? ??? ??? ?deleteNode(node);
?? ??? ??? ?auto pos1 = m_l.find(key);
?? ??? ??? ?m_l.erase(pos1);
?? ??? ??? ?m_l[key] = insertNode(key);
?? ??? ??? ?return;
?? ??? ?}
?? ??? ?if (curSize == size)
?? ??? ?{
?? ??? ??? ?int tmp = head->value;
?? ??? ??? ?Node *node = m_l[tmp];
?? ??? ??? ?auto pos = m.find(tmp);
?? ??? ??? ?m.erase(pos);
?? ??? ??? ?deleteHead();
?? ??? ??? ?auto pos1 = m_l.find(tmp);
?? ??? ??? ?m_l.erase(pos1);

?? ??? ?}
?? ??? ?m[key] = value;
?? ??? ?Node *node = m_l[key];
?? ??? ?m_l[key] = insertNode(key);
?? ?}
};

?