LeetCode146 LRU 缓存

链接: https://leetcode-cn.com/problems/lru-cache/description/

题意

请你设计并实现一个满足 LRU (最近最少使用)缓存约束的数据结构
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行

解法一

要求设计一个这样的数据结构 可以维护最久未访问的一个队列
我一开始想到的是用一个双向队列 队列尾放最新的 队列头放最久未使用的
同时需要记录当前数的有没有被放到队尾 以处理后序需要删除队头元素
挺麻烦的 但是最终也实现了

代码

class LRUCache {
public:
    int siz;
    int cap;
    unordered_map<int, int> lru;
    unordered_map<int, int> times;
    deque<int> dq;
    LRUCache(int capacity) {
        cap = capacity;
        siz = 0;
    }
    
    int get(int key) {
        if (times[key] == 0) return -1;
        else {
            dq.push_back(key);
            times[key]++;
        }
        return lru[key];
    }
    
    void put(int key, int value) {
        if (times[key] != 0) { // cache hit
            dq.push_back(key);
            lru[key] = value;
            times[key]++;
        }
        else { // cache miss
            if (siz < cap) { // 如果容量未满
                dq.push_back(key);
                lru[key] = value;
                times[key]++;
                siz++;
            }
            else { // 如果容量满了
                while(dq.size()) {
                    int front = dq.front();
                    dq.pop_front();
                    times[front]--;
                    if (times[front] == 0) {
                        lru[front] = 0;
                        break;
                    }
                }
                dq.push_back(key);
                times[key]++;
                lru[key] = value;
            }           
        }
    }
};

解法二

但是上面的解法可能存在大量冗余值 且可能在删除最久未使用的值的时候产生无效开销
需要找到一个更好的数据结构 可以维护最久未访问的一个队列
同时需要把最新访问的节点放到最前面
数组无法实现在O(1)时间内完成这样的操作 因为每次移动需要调整整个数组 时间复杂度接近O(n)
比较直观的想法是用到map，可以根据key的值在O(1)或者O(logn)时间内访问到元素
考虑到需要修改线性表的顺序 用链表是最好的
因为链表可以在O(1)完成节点的添加和删除 很好的满足了题目的要求
最终确定数据结构unordered_map + 双向链表
然后就是实现的过程了
双向链表需要实现一个将元素添加到头部，删除任一节点，删除尾节点这几个方法
同时添加链表头节点和尾节点 便于节点操作处理

代码

class Node { // 双向链表节点
public:
    Node* prev;
    Node* next;
    int key;
    int val;
    Node(int key, int val) {
        this -> key = key;
        this -> val = val; 
    }
};

class DLinkedList { // 双向链表
public:
    Node* head;
    Node* tail;
    DLinkedList() {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head -> next = tail;
        tail -> prev = head;
    }
    void addFirst(Node* node) { // 置于头部
        node -> next = head -> next;
        node -> prev = head;
        head -> next -> prev = node;
        head -> next = node;
    }

    int deleteNode(Node* node) { // 删除节点
        int key = node -> key;
        node -> prev -> next = node -> next;
        node -> next -> prev = node -> prev;
        return key;
    }
    int deleteLast() {
        if (head -> next == tail) return -1; // 此时链表为空
        return deleteNode(tail -> prev);
    }

};

class LRUCache {
public:
    unordered_map<int, Node*> mp;
    int cap;
    DLinkedList* cache;
    LRUCache(int capacity) {
        cap = capacity;
        cache = new DLinkedList();
    }
    
    int get(int key) {
        if (mp.find(key) == mp.end()) { // 如果找不到节点 return -1
            return -1;
        }
        int val = mp[key] -> val;
        put(key, val); // 更新节点位置 置于cache头部
        return val; 
    }
    
    void put(int key, int value) {
        Node* newNode = new Node(key, value);
        if (mp.find(key) != mp.end()) { // 如果节点存在 
            cache -> deleteNode(mp[key]); // 删除原先节点
            mp[key] = newNode;          // 更新cache值
            cache -> addFirst(newNode); // 将节点置于表头
        }
        else {
            if (mp.size() == cap) { // cache已满
                int k = cache -> deleteLast(); // 删除末尾节点
                mp.erase(k); // 从cache中删除
            }
            mp[key] = newNode; // 更新cache值
            cache -> addFirst(newNode); // 置于表头
        }
    }
};