Design a data structure that follows the constraints of a Least Recently Used (LRU) cache .
Implement the LRUCache class:
LRUCache(int capacity) Initialize the LRU cache with positive size capacity .int get(int key) Return the value of the key if the key exists, otherwise return -1 .void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.Follow up: Could you do get and put in O ( 1 ) O(1) O(1) time complexity?
Example 1:
Input ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] Output [null, null, null, 1, null, -1, null, -1, 3, 4] Explanation LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // cache is {1=1} lRUCache.put(2, 2); // cache is {1=1, 2=2} lRUCache.get(1); // return 1 lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3} lRUCache.get(2); // returns -1 (not found) lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3} lRUCache.get(1); // return -1 (not found) lRUCache.get(3); // return 3 lRUCache.get(4); // return 4Constraints:
1 <= capacity <= 30000 <= key <= 30000 <= value <= 104At most 3 * 104 calls will be made to get and put .题意：实现LRU Cache数据结构，即最近最少使用机制，操作系统中用于虚拟内存管理的一种调度算法。
为了实现 O ( 1 ) O(1) O(1) 的读 get 和写 put 操作，需要将哈希映射和双向链表结合起来。其中，哈希映射记录关键字 key 到链表结点地址的映射，用于 get 操作。写入数据时，如果关键字 key 可以通过哈希映射查找到，则直接修改其值；如果不存在，则插入数据到双向链表的尾部。
更重要的是，为了实现LRU机制，判断数据最近被使用与否，我们需要对双向链表进行操作。在 get 时如果数据存在，则将该结点移动到双向链表的末尾；在 put 时，如果数据存在则进行同样的操作，如果数据不存在则直接插入到双向链表的尾部，此时如果超出LRU缓存容量，则删除双向链表首结点（即最久未被使用的数据）。
当然，如果访问数据时将结点移动到双向链表头部、插入到链表头部、删除链表尾结点，也是可行的做法。具体代码如下：
struct DoubleLinkedList { DoubleLinkedList *prev, *next; int key, value; DoubleLinkedList(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {} }; class LRUCache { private: DoubleLinkedList *head; //虚拟表头结点 DoubleLinkedList *tail; //虚拟表尾结点 unordered_map<int, DoubleLinkedList*> memoryCache; //缓存,记录key所对应的链表结点 int _capacity = 0; void removeNode(DoubleLinkedList *node) { //从双向链表中删除该结点 node->prev->next = node->next; node->next->prev = node->prev; } void pushNodeBack(DoubleLinkedList *node) { //将该结点插入双向链表表尾 node->prev = tail->prev; tail->prev->next = node; node->next = tail; tail->prev = node; } public: LRUCache(int capacity) { _capacity = capacity; head = new DoubleLinkedList(-1, -1); tail = new DoubleLinkedList(-1, -1); head->next = tail; tail->prev = head; } //如果缓存中查找到key,则需更新该key为最近使用(即放到表尾) int get(int key) { if (memoryCache.find(key) != memoryCache.end()) { DoubleLinkedList *node = memoryCache[key]; removeNode(node); //从双向链表中移除该结点 pushNodeBack(node); //将该结点放至表尾 return node->value; } return -1; } //如果缓存中查找到key,则需更新该key的值,同时更新为最近使用(即放到表尾) void put(int key, int value) { if (memoryCache.find(key) != memoryCache.end()) { DoubleLinkedList *node = memoryCache[key]; //获取该key对应的结点指针 removeNode(node); //从双向链表中移除该结点 pushNodeBack(node); //将该结点放至表尾 node->value = value; //修改结点对应的值 } else { if (memoryCache.size() == _capacity) { //如果缓存已满 int topKey = head->next->key; //获取链表头结点的key DoubleLinkedList *temp = head->next; //保存链表首元素结点的指针 removeNode(head->next); //移除链表的首元素结点 delete temp; //回收内存占用 memoryCache.erase(topKey); //同时从cache中移除该key } DoubleLinkedList *node = new DoubleLinkedList(key, value); pushNodeBack(node); //表尾插入新key:value memoryCache[key] = node; //存入缓存 } } };提交后效率如下：
执行用时：160 ms, 在所有 C++ 提交中击败了99.54% 的用户 内存消耗：39.4 MB, 在所有 C++ 提交中击败了21.61% 的用户