本文共 4029 字，大约阅读时间需要 13 分钟。

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)$ 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]ExplanationLRUCache 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 1lRUCache.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 3lRUCache.get(4);    // return 4

Constraints:

• 1 <= capacity <= 3000
• 0 <= key <= 3000
• 0 <= value <= 104
• At most 3 * 104 calls will be made to get and put .

题意：实现LRU Cache数据结构，即最近最少使用机制，操作系统中用于虚拟内存管理的一种调度算法。

解法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
   
     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% 的用户

转载地址：https://memcpy0.blog.csdn.net/article/details/109188260 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！