JZOffer-II-031

刷题

发布日期: 2022-06-06

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

1 题目描述

题目链接：剑指 Offer 62. 圆圈中最后剩下的数字

运用所掌握的数据结构，设计和实现一个 LRU (Least Recently Used，最近最少使用) 缓存机制 。

实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

示例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

2 思路

用一个双向链表即可实现删除、插入的复杂度为O(1)，为实现查找的时间复杂度也为O(1)（链表的查找为O(n), n为节点数）, 则添加一个哈希表来实现key与链表节点位置的映射。
因此，调用put的时候就先查找当前的key是否存在于哈希表中，若不存在说明需要插入新的节点，这时候需要考虑当前链表中的节点数，这个可以用一个全局变量size来记录，而容量为cap，当需要插入新的节点，而size==cap时，则需要将链表尾的节点删掉，然后将新的节点加到链表头；否则，直接将新的节点加到链表头即可。而当当前的key已经存在时，则通过哈希映射找到对应的节点，并将该节点的val值更新为输入量value,并将该节点移到链表头。

struct MyLinkedList{
    int key, val;
    MyLinkedList *next, *prev;
    MyLinkedList(): key(0), val(0), next(nullptr), prev(nullptr) {}
    MyLinkedList(int _key, int _val): key(_key), val(_val), next(nullptr), prev(nullptr) {}
};

class LRUCache {
    unordered_map<int, struct MyLinkedList*> m;
    struct MyLinkedList* dummyHead, *dummyTail;
    int size;   // 当前链表节点数
    int cap;    // LRU容量
public:
    LRUCache(int capacity) {
        size = 0;   // 初始节点数为0
        dummyHead = new struct MyLinkedList();  // 虚拟头结点
        dummyTail = new struct MyLinkedList();  // 虚拟尾节点
        dummyHead->next = dummyTail;
        dummyTail->prev = dummyHead;
        cap = capacity;                         // 初始化容量
    }
    
    int get(int key) {
        // 通过哈希查找是否已经存在该key
        if(!m.count(key)){      // 不存在返回-1
            return -1;
        }
        // 存在，通过哈希映射查找节点位置
        struct MyLinkedList* it = m[key];
        // 将节点从该位置取出(修改其前后节点指向)
        it->prev->next = it->next;
        it->next->prev= it->prev;
        // 将节点移动到链表头
        it->next = dummyHead->next;
        dummyHead->next->prev = it;
        it->prev = dummyHead;
        dummyHead->next = it;
        return it->val;
    }
    
    void put(int key, int value) {
        // key已经存在于哈希表中
        if(m.count(key)){
            struct MyLinkedList* it = m[key];
            // 更新数据
            it->val = value;
            // 将节点从该位置取出(修改其前后节点指向)
            it->prev->next = it->next;
            it->next->prev = it->prev;
            // 将节点移动到链表头
            it->next = dummyHead->next;
            dummyHead->next->prev = it;
            it->prev = dummyHead;
            dummyHead->next = it;
            return;
        }
        // key不存在
        struct MyLinkedList* newNode = new struct MyLinkedList(key, value);
        // 判断是否容量已经满了
        if(size == cap){
            // 满了，需要将链表尾删去
            struct MyLinkedList* tmpNode = dummyTail->prev;
            // 并将该节点的key从哈希表中删除
            m.erase(tmpNode->key);
            // 将该节点从链表中取出(修改其前后节点指向)
            tmpNode->prev->next = tmpNode->next;
            tmpNode->next->prev = tmpNode->prev;
            delete tmpNode;     // 防止内存泄漏
            size--;             // 删掉一个节点，节点数-1
        }
        // 插入新节点到链表头
        newNode->next = dummyHead->next;
        dummyHead->next->prev = newNode;
        newNode->prev = dummyHead;
        dummyHead->next = newNode;
        // 添加到哈希表中
        m[key] = newNode;
        size++;                 // 插入一个新节点，节点数+1
    }
};

由于put中存在将节点移到链表头，get同样存在这个操作，可以将这个操作封装为一个函数moveToHead()，而节点移到链表头其实可以看作将该节点删除后再将节点插到链表头，put中也存在删除节点的操作，因而可以进一步封装一个函数remove(),因此：moveToHead() = remove() + addToHead().

struct MyLinkedList{
    int key, val;
    MyLinkedList *next, *prev;
    MyLinkedList(): key(0), val(0), next(nullptr), prev(nullptr) {}
    MyLinkedList(int _key, int _val): key(_key), val(_val), next(nullptr), prev(nullptr) {}
};

class LRUCache {
    unordered_map<int, struct MyLinkedList*> m;
    struct MyLinkedList* dummyHead, *dummyTail;
    int size;
    int cap; 
public:
    LRUCache(int capacity) {
        size = 0;
        dummyHead = new struct MyLinkedList();
        dummyTail = new struct MyLinkedList();
        dummyHead->next = dummyTail;
        dummyTail->prev = dummyHead;
        cap = capacity;
    }
    
    int get(int key) {
        if(!m.count(key)){
            return -1;
        }
        struct MyLinkedList* it = m[key];
        moveToHead(m[key]);
        return it->val;
    }
    
    void put(int key, int value) {
        if(m.count(key)){
            struct MyLinkedList* it = m[key];
            it->val = value;
            return;
        }
        struct MyLinkedList* newNode = new struct MyLinkedList(key, value);
        if(size == cap){
            struct MyLinkedList* tmpNode = dummyTail->prev;
            m.erase(tmpNode->key);
            remove(tmpNode);
            delete tmpNode;
            size--;
        }
        size++;
        addToHead(newNode);
        m[key] = newNode;
    }

    void remove(struct MyLinkedList* node){
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void addToHead(struct MyLinkedList* node){
        node->next = dummyHead->next;
        dummyHead->next->prev = node;
        node->prev = dummyHead;
        dummyHead->next = node;
    }

    void moveToHead(struct MyLinkedList* node){
        remove(node);
        addToHead(node);
    }
};