设计LRU缓存结构

这是一道类的设计题，此类题目要求我们理解各个基本数据结构的用法及其复杂度，并且学会组合它们：

1. 存储键值对——map/unordered_map
2. 存储集合——set/unordered_set
3. 查找最大/最小/topk值——大顶堆/小顶堆/平衡二叉树
4. 序列结构——数组&链表
5. 字符串索引——trie树（百度常考）

本题要求get和set的时间复杂度都是O(1)，我们可以采用unordered_map和双向链表的组合数据结构，原理如下图：

对于两个操作的解释如下：

• set操作：
  1. 如果key存在于map中，更新value，然后把节点移到双向链表头部
  2. 如果key不在map中且没有溢出，直接构建新节点并插入链表首部
  3. 如果key不再map中但是有溢出，删除最后一个节点，再构建新节点插入链表首部
• get操作：
  1. 如果找到了，将节点移到首部并返回对应value
  2. 如果没找到，返回-1

代码如下：

//
// Created by jt on 2020/9/15.
//
#include <vector>
#include <unordered_map>
using namespace std;

struct DNode{
    DNode *pre, *next;
    int key, val;
    DNode(int k, int v): pre(nullptr), next(nullptr), key(k), val(v) {}
};

class LRUCache{
public:
    explicit LRUCache(int n): n(n){}
    int getVal(int key) {
        if (mp.count(key)) {
            setVal(key, mp[key]->val);  // 将节点移到首部
            return mp[key]->val;
        }
        else return -1;
    }
    void setVal(int key, int val) {
        if (mp.count(key)) {
            // 如果key存在，直接更新
            updateExisted(key, val);
        } else {
            // 如果key不存在，考虑缓存大小
            if (mp.size() == n) {
                // 如果缓存已满，清除最久的那个元素
                removeLast();
            }
            addFirst(key, val);
        }
    }
private:
    int n;
    unordered_map<int, struct DNode*> mp;
    struct DNode* head = nullptr, *tail = nullptr;
    void updateExisted(int key, int val) {
        mp[key]->val = val;
        if (mp[key] == head) return;
        if (mp[key] == tail) tail = mp[key]->pre;
        if (mp[key]->next) mp[key]->next->pre = mp[key]->pre;
        if (mp[key]->pre) mp[key]->pre->next = mp[key]->next;
        mp[key]->pre = nullptr;
        mp[key]->next = head;
        head->pre = mp[key];
        head = mp[key];
    }
    void removeLast() {
        int key = tail->key;
        if (tail->pre) tail->pre->next = nullptr;
        tail = tail->pre;
        delete mp[key];
        mp.erase(key);
    }
    void addFirst(int key, int val) {
        auto* tmp = new DNode(key, val);
        mp[key] = tmp;
        if (!tail && !head) { head = tail = tmp; return; }
        tmp->next = head;
        head->pre = tmp;
        head = tmp;
    }
};

class Solution {
public:
    /**
     * 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
        LRUCache lru(k);
        vector<int> res;
        for (auto vec : operators) {
            if (vec[0] == 1) {
                lru.setVal(vec[1], vec[2]);
            } else {
                res.push_back(lru.getVal(vec[1]));
            }
        }
        return res;
    }
};