• 【LeetCode刷题】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

    思路：这道题的难点在于记录最近最少使用，使用map可以满足get的O(1)，但是无法记录最近最少使用的数据；如果使用数组，删除/增加的时间复杂度则是O(n)，也不满足。

    使用哈希表 + 双向链表可以满足删除/增加的时间复杂度为O(1)。

    这个图太形象了。

    （1）双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。

    （2）哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。

    （3）对于 get 操作，首先判断 key 是否存在：

            （a）如果 key 不存在，则返回 −1；

            （b）如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。

    （3）对于 put 操作，首先判断 key 是否存在：

            （a）如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；

            （b）如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。

    思路很清晰

    1. class LRUCache {
    2. public:
    3.     LRUCache(int capacity) {
    4.  
    5.     }
    6.     
    7.     int get(int key) {
    8.  
    9.     }
    10.     
    11.     void put(int key, int value) {
    12.  
    13.     }
    14. };
    15.  
    16. /**
    17.  * Your LRUCache object will be instantiated and called as such:
    18.  * LRUCache* obj = new LRUCache(capacity);
    19.  * int param_1 = obj->get(key);
    20.  * obj->put(key,value);
    21.  */

    一步步实现：

    （1）定义双链表

    1. struct DLinkedNode {
    2.     int key, value;             // k-v
    3.     DLinkedNode* prev;          // 前向指针
    4.     DLinkedNode* next;          // 后向指针
    5.     // 两个构造函数
    6.     DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
    7.     DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
    8. };

    （2）在LRUCache类中添加成员属性：哈希表+双向链表

    1. class LRUCache {
    2. public:
    3.     // 新加的
    4.     unordered_map<int, DLinkedNode*> cache;
    5.     DLinkedNode* head;            // 伪头节点，不存数据
    6.     DLinkedNode* tail;            // 伪尾节点，不存数据
    7.     int size;                     // 当前存储的数量，当size==capacity时，要移出数据了
    8.     int capacity;                 // 容量
    9.  
    10.     // 实现构造函数
    11.     LRUCache(int _capacity): capacity(_capacity), size(0) {
    12.         // 使用伪头节点和伪尾节点，不存数据
    13.         head = new DLinkedNode();
    14.         tail = new DLinkedNode();
    15.         // 开始时一个数据都没有
    16.         head->next = tail;
    17.         tail->prev = head;
    18.     }
    19.     
    20.     int get(int key) {
    21.  
    22.     }
    23.     
    24.     void put(int key, int value) {
    25.  
    26.     }
    27. };

    （3）实现双向链表中的【在头部添加数据】、【任意位置删除数据】、【数据移动到头部】、【从尾部删除数据】

    在头部添加数据

    1.     // 在头部添加数据
    2.     void addToHead(DLinkedNode* node) {
    3.         node->prev = head;
    4.         node->next = head->next;
    5.         head->next->prev = node;
    6.         head->next = node;
    7.     }

    任意位置删除数据

    1.     // 任意位置删除数据
    2.     void removeNode(DLinkedNode* node) {
    3.         node->prev->next = node->next;
    4.         node->next->prev = node->prev;
    5.     }

    数据移动到头部

    1.     // 移动数据到头部
    2.     void moveToHead(DLinkedNode* node) {
    3.         removeNode(node);
    4.         addToHead(node);
    5.     }

    从尾部删除数据

    1.     // 从尾部删除数据
    2.     DLinkedNode* reoveTail() {
    3.         DLinkedNode* node = tail->prev;
    4.         removeNode(node);
    5.         return node;
    6.     }

    （4）实现get函数

    如果不存在直接返回-1，存在的话，先通过哈希表定位，再移动到头部

    1.     int get(int key) {
    2.         // 不存在
    3.         if (cache.count(key) == 0) {
    4.             return -1;
    5.         }
    6.         // 通过哈希找到，移动到头部
    7.         DLinkedNode* node = cache[key];
    8.         moveToHead(node);
    9.         return node->value;
    10.     }

    （5）实现put函数

    如果key不存在，则创建一个节点，注意size==capacity的情况，此时删除队尾数据

    靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。

    如果存在，修改value，再将该节点移动到队头

    1.  void put(int key, int value) {
    2.         // 不存在
    3.         if (cache.count(key) == 0) {
    4.             DLinkedNode* node = new DLinkedNode(key, value);
    5.             cache[key] = node;          // 添加到哈希表中
    6.             addToHead(node);            // 移动到队头
    7.             size++;
    8.             if (size > capacity) {
    9.                 DLinkedNode* removeNode = reoveTail();  // 删除尾部数据
    10.                 cache.erase(removeNode->key);           // 删除哈希中的数据
    11.                 delete removeNode;
    12.                 size--; 
    13.             }
    14.         } else {
    15.             DLinkedNode* node = cache[key];
    16.             node->value = value;
    17.             moveToHead(node);               // 移到队头
    18.         }
    19.     }

    全部代码实现

    1. struct DLinkedNode {
    2.     int key, value;             // k-v
    3.     DLinkedNode* prev;          // 前向指针
    4.     DLinkedNode* next;          // 后向指针
    5.     // 两个构造函数
    6.     DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
    7.     DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
    8. };
    9.  
    10. class LRUCache {
    11. public:
    12.     unordered_map<int, DLinkedNode*> cache;
    13.     DLinkedNode* head;
    14.     DLinkedNode* tail;
    15.     int size;
    16.     int capacity;
    17.  
    18.  
    19.     LRUCache(int _capacity): capacity(_capacity), size(0) {
    20.         // 使用伪头节点和伪伪节点，不存数据
    21.         head = new DLinkedNode();
    22.         tail = new DLinkedNode();
    23.         // 开始时一个数据都没有
    24.         head->next = tail;
    25.         tail->prev = head;
    26.     }
    27.     
    28.     int get(int key) {
    29.         // 不存在
    30.         if (cache.count(key) == 0) {
    31.             return -1;
    32.         }
    33.         // 通过哈希找到，移动到头部
    34.         DLinkedNode* node = cache[key];
    35.         moveToHead(node);
    36.         return node->value;
    37.     }
    38.     
    39.     void put(int key, int value) {
    40.         // 不存在
    41.         if (cache.count(key) == 0) {
    42.             DLinkedNode* node = new DLinkedNode(key, value);
    43.             cache[key] = node;          // 添加到哈希表中
    44.             addToHead(node);            // 移动到队头
    45.             size++;
    46.             if (size > capacity) {
    47.                 DLinkedNode* removeNode = reoveTail();  // 删除尾部数据
    48.                 cache.erase(removeNode->key);           // 删除哈希中的数据
    49.                 delete removeNode;
    50.                 size--; 
    51.             }
    52.         } else {
    53.             DLinkedNode* node = cache[key];
    54.             node->value = value;
    55.             moveToHead(node);               // 移到队头
    56.         }
    57.     }
    58.  
    59.     // 在头部添加数据
    60.     void addToHead(DLinkedNode* node) {
    61.         node->prev = head;
    62.         node->next = head->next;
    63.         head->next->prev = node;
    64.         head->next = node;
    65.     }
    66.  
    67.     // 任意位置删除数据
    68.     void removeNode(DLinkedNode* node) {
    69.         node->prev->next = node->next;
    70.         node->next->prev = node->prev;
    71.     }
    72.  
    73.     // 移动数据到头部
    74.     void moveToHead(DLinkedNode* node) {
    75.         removeNode(node);
    76.         addToHead(node);
    77.     }
    78.  
    79.     // 从尾部删除数据
    80.     DLinkedNode* reoveTail() {
    81.         DLinkedNode* node = tail->prev;
    82.         removeNode(node);
    83.         return node;
    84.     }
    85.  
    86.  
    87. };
    88.  
    89. /**
    90.  * Your LRUCache object will be instantiated and called as such:
    91.  * LRUCache* obj = new LRUCache(capacity);
    92.  * int param_1 = obj->get(key);
    93.  * obj->put(key,value);
    94.  */

    参考：【字节一面】 LRU Cache 实现剖析_哔哩哔哩_bilibili

    链接：. - 力扣（LeetCode）

  • 相关阅读:
    问题记录v(●‘◡‘●)v
    猿创征文 | MyBatis与MyBatis-Plus的区别
    Qt之xml文件解析
    代码提交没有记录到github activity和contribute
    神经网络算法有哪些模型,神经网络模型数据处理
    python自动化测试——unittest二次开发之根据不同的粒度实现多线程执行测试用例（一）
    关于 Eclipse 的一场 “三角关系”
    想要精通算法和SQL的成长之路 - 填充书架
    【保姆级】新机器部署Nginx
    【附源码】计算机毕业设计JAVA超市货品进销存系统前台
  • 原文地址：https://blog.csdn.net/Zhouzi_heng/article/details/136332367