实现LRUCache

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

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

// 结点类
struct Node {int key_, value_;Node *prev, *next;Node(int k = 0, int v = 0): key_(k), value_(v), prev(nullptr), next(nullptr) {}
};class LRUCache {
public:int size_, cap_;Node *head, *tail;unordered_map<int, Node *> h;LRUCache(int capacity) {size_ = 0;cap_ = capacity;head = new Node();tail = new Node();head->next = tail;tail->prev = head;}int get(int key) {if(!h.count(key)) {return -1;} else { // 访问一个元素后，将其移动到头结点RemoveNode(h[key]);AddNodeToHead(h[key]);return h[key]->value_;}}void put(int key, int value) {if(h.count(key)) {RemoveNode(h[key]);AddNodeToHead(h[key]);h[key]->value_ = value;} else {if(size_ == cap_) { // LRU容量不够，删除链表尾元素h.erase(tail->prev->key_);RemoveNode(tail->prev);size_--;}h[key] = new Node(key, value);AddNodeToHead(h[key]);size_++;}}// 从双向链表中删除某个结点void RemoveNode(Node *node) {node->prev->next = node->next;node->next->prev = node->prev;}// 将node插入到头结点之后void AddNodeToHead(Node *node) {node->prev = head;node->next = head->next;head->next->prev = node;head->next = node;}
};