实现 LRU 缓存数据结构。

参考：牛客 - 设计 LRU 缓存结构 、力扣 - 146 LRU 缓存机制

• 哈希表 + 双向链表
• 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
• 哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。

struct DListNode {
    int key, val;
    DListNode* pre;
    DListNode* next;
    DListNode(int k, int v) : key(k), val(v), pre(nullptr), next(nullptr) {}
}; // 双向链表

class Solution {
private:
    int capacity = 0;
    int size = 0;
    DListNode* head;
    DListNode* tail;
    unordered_map<int, DListNode*> mp; 
    
public:
    int get(int key) {
        int ret = -1;
        if (mp.find(key) != mp.end()) {
            ret = mp[key]->val;
            moveToHead(mp[key]);
        }
        return ret;
    }
    
    void set(int key, int val) {
        if (mp.find(key) == mp.end()) {
            // 如果 key 不存在，创建一个新的节点
            DListNode* node = new DListNode(key, val);
            // 添加进哈希表
            mp[key] = node;
            // 添加至双向链表的头部
            addToHead(node);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DListNode* delNode = removeTail();
                // 删除哈希表中对应项
                mp.erase(delNode->key);
                delete delNode;
                --size;
            }
        }
        else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            DListNode* node = mp[key];
            node->val = val;
            moveToHead(node);
        }
    }
    
    void addToHead(DListNode* node) {
        node->pre = head;
        node->next = head->next;
        head->next->pre = node;
        head->next = node;
    }
    
    void removeNode(DListNode* node) {
        node->pre->next = node->next;
        node->next->pre = node->pre;
    }
    
    void moveToHead(DListNode* node) {
        removeNode(node);
        addToHead(node);
    }
    
    DListNode* removeTail() {
        DListNode* node = tail->pre;
        removeNode(node);
        return node;
    }
    
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        // write code here
        if (k < 1) return {};
        this->capacity = k;
        // 使用伪头部和伪尾部节点
        this->head = new DListNode(0,0);
        this->tail = new DListNode(0,0);
        this->head->next = this->tail;
        this->tail->pre = this->head;
        
        if (operators.size() == 0) return {};
        
        vector<int> res;
        for (auto& op : operators) {
            if (op[0] == 1) {
                set(op[1], op[2]);
            } else if (op[0] == 2) {
                int value = get(op[1]);
                res.push_back(value);
            }
        }
        return res;
    }
};

纯 LRU 算法

class LRUCache {
    list<pair<int, int>> cache;//创建双向链表
    unordered_map<int, list<pair<int, int>>::iterator> map;//创建哈希表
    int cap;
public:
    LRUCache(int capacity) {
        cap = capacity;
    }

    int get(int key) {
        if (map.count(key) > 0){
            auto temp = *map[key];
            cache.erase(map[key]);
            map.erase(key);
            cache.push_front(temp);
            map[key] = cache.begin();//映射头部
            return temp.second;
        }
        return -1;
    }

    void put(int key, int value) {
        if (map.count(key) > 0){
            cache.erase(map[key]);
            map.erase(key);
        }
        else if (cap == cache.size()){
            auto temp = cache.back();
            map.erase(temp.first);
            cache.pop_back();
        }
        cache.push_front(pair<int, int>(key, value));
        map[key] = cache.begin();//映射头部
    }
};

/**
 * 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);
 */