剑指OfferII031.最近最少使用缓存

运用所掌握的数据结构，设计和实现一个 LRU (Least Recently Used，最近最少使用) 缓存机制 。
实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

示例：

输入["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); // 返回 1lRUCache.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); // 返回 3lRUCache.get(4); // 返回 4

提示：

1 <= capacity <= 30000 <= key <= 100000 <= value <= 105最多调用 2 * 105 次 get 和 put

进阶：是否可以在 O(1) 时间复杂度内完成这两种操作？

这个题，说难不难，主要就是麻烦。
首先可以用哈希表实现 get 和 put 操作，时间复杂度都为 O(1)，但是普通哈希表无法找到最近最少使用的键。因此，需要在哈希表的基础上进行修改。

因为要实现删除最近最少使用的键，很明显这个键位置是随机的，而这种任意位置的删除操作，用链表来做是最合适的，因此本题可以使用个双向链表来对哈希表进行补充。

因为需要知道缓存内最近最少使用的元素，因此可以把存入的元素按访问的先后顺序存入双向链表。每次访问一个元素，无论是 put 还是 get 操作，都把该元素移动到链表的尾部。这样就可以保证链表的头部就是最近最少使用的元素。在实现了最近最少使用的功能后，在加入哈希表就可以实现 get 和 put 操作时间复杂度为 O(1)。具体来讲就是，哈希表内存在 key → 对应链表节点的指针，得到对应的指针便可以操作节点内的 key 和 value 值。

代码：

class LRUCache {private: struct ListNode{ int key; int val; ListNode* next = nullptr; ListNode* prev = nullptr; ListNode(){} ListNode(int x,int y): key(x),val(y) {} };private: int capacity; ListNode* tail; ListNode* dummy; map hash;private: void moveToTail(int key) { ListNode* cur = hash[key]; if(cur == tail) return; cur->prev->next = cur->next; cur->next->prev = cur->prev; cur->prev = tail; tail->next = cur; tail = cur; } void insertToTail(int key, int value) { ListNode* cur = new ListNode(key,value); tail->next = cur; cur->prev = tail; tail = cur; hash[key] = tail; } void popFromHead(int newKey, int newValue) { hash.erase(dummy->next->key); dummy->next->key = newKey; dummy->next->val = newValue; hash[newKey] = dummy->next; moveToTail(newKey); }public: LRUCache(int capacity) { this->capacity = capacity; dummy = new ListNode(); tail = dummy; } int get(int key) { if(!hash.count(key)) return -1; moveToTail(key); return hash[key]->val; } void put(int newKey, int newValue) { if(hash.count(newKey)) { hash[newKey]->key = newKey; hash[newKey]->val = newValue; moveToTail(newKey); return; } if(hash.size() < this->capacity) { insertToTail(newKey,newValue); } else if(hash.size() == this->capacity) { popFromHead(newKey,newValue); } }};

另外，看到其他大佬的解答后，发现list的实质也是双向链表，能够想到这个办法的大佬，c++基础可太强了，下边附上大佬的代码：

class LRUCache {public: list> list1; //双向链表 int capacity; unordered_map>::iterator > key_list_ptr; LRUCache(int capacity) { this->capacity = capacity; } int get(int key) { if (key_list_ptr.find(key) == key_list_ptr.end()) return -1; auto [k, v] = * key_list_ptr[key]; list1.erase(key_list_ptr[key]); list1.push_back(pair{k, v}); key_list_ptr[key] = --list1.end(); return v; } void put(int key, int value) { if (key_list_ptr.find(key) != key_list_ptr.end()) list1.erase(key_list_ptr[key]); list1.push_back(pair{key, value}); key_list_ptr[key] = --list1.end(); if (list1.size() > capacity) { key_list_ptr.erase(list1.begin()->first); list1.pop_front(); } }};