剑指 Offer II 031. 最近最少使用缓存

题目链接

剑指 Offer II 031. 最近最少使用缓存 mid

题目描述

运用所掌握的数据结构，设计和实现一个 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); // 返回
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

提示：

• $1<=capacity<=3000$
• $0<=key<=10000$
• $0<=value<=10^5$
• 最多调用 $2\ast 10^5$ 次 get和 put

解法：双向链表 + 哈希表

链表结点Node的设计：

       struct Node{
           int key = 0;
           int val = 0;
           Node * prev = nullptr;
           Node * next = nullptr;
           Node(){}
           Node(int k,int v) : key(k),val(v){}
       };

我们用一个哈希表 m存储 [key，key对应的结点Node]。

我们默认链表的头节点是 最近最少使用的 ，所以一旦容量满了再插入新节点时，就需要删除头节点，同时删除头节点在 m中的记录。新节点插入到链表尾，m增加新插入结点的记录。

查询了一个已经存在链表中的结点之后，需要把它移动到链表尾部，因为使用过了。

时间复杂度 ： $O(n)$

C++代码：

class LRUCache {
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        this->sz = 0;
        dummy = new Node();
        tail = dummy;
    }
    
    int get(int key) {
        if(!m.count(key)) return -1;
        moveToTail(key);
        return m[key]->val;
    }
    
    void put(int key, int value) {
        if(m.count(key)){
            m[key]->val = value;
            moveToTail(key);
        }
        else if(sz < capacity){
            addToTail(key,value);
            m[key] = tail;
            sz++;
        }
        else{
            deleteHead(key,value);
        }
    }

private:   
       struct Node{
           int key = 0;
           int val = 0;
           Node * prev = nullptr;
           Node * next = nullptr;
           Node(){}
           Node(int k,int v) : key(k),val(v){}
       };
       //最大容量
       int capacity;
       //链表中结点的数量
       int sz;
       //虚拟头节点，避免边界问题
       Node * dummy;
       //尾节点
       Node * tail;
       unordered_map<int,Node*> m;

       void moveToTail(int key){
           Node * node = m[key];
           
           //已经是尾节点 就直接返回
           if(node == tail) return;

           //删除node结点 
           //让node的前驱结点 直接 指向node的后继结点
           //让node的后继结点 直接 指向node的前驱结点
           node->prev->next = node->next;
           node->next->prev = node->prev;

           node->next = nullptr;
           node->prev = nullptr;

           //把 node 结点插入到尾节点
           node->prev = tail;
           tail->next = node;
           tail = node;
       }
       
       //新插入一个结点到尾结点
       void addToTail(int key,int val){
           Node * node = new Node(key,val);
           tail->next = node;
           node->prev = tail;
           tail = node;
           m[key] = tail;
       }
       //为了避免边界问题，我们不实际删除头节点，只用删除 m 中头节点的记录
       //把头节点的值 改为 新插入结点的 key 和 val，再移动到链表尾部
       void deleteHead(int key,int val){
           Node * node = dummy->next;
           m.erase(node->key);
           dummy->next->key = key;
           dummy->next->val = val;
           m[key] = dummy->next;
 
           moveToTail(key);
       }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */