题意整理:

本题要求设计一个LRU缓存结构，LRU即为最近最少使用算法，既缓存中保存的数据以使用顺序进行排序，缓存淘汰时选中最久为使用的进行淘汰

方法一：哈希表+双向链表

核心思想：

LRU 缓存结构可以通过使用一个哈希表和一个双向链表维护所有在缓存中的键值对实现。
双向链表按照键值对被使用的顺序进行存储了，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
哈希表负责通过缓存数据的键映射到其在双向链表中的位置，使得定位操作复杂度为。
对一个操作，首先使用哈希表进行定位，找出其在双向链表中的位置，随后将其移动到双向链表的头部，即实现 的时间内完成 或者 操作。
具体实现： :如果不存在，返回 ；如果 存在，则 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。 ：如果 不存在，创建一个新的节点，在双向链表的头部添加该节点，并将 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项。
如果 存在，则先通过哈希表定位，再将对应的节点的值进行更新，并将该节点移到双向链表的头部。

核心代码：

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

class Solution {
private:
    unordered_map<int, Node*> mp;//用于快速查找键值对
    Node* head = nullptr;//头节点
    Node* tail = nullptr;//尾节点
    int cap;//容量
    int size;//当前大小
public:
    void deleteNode(Node* p) {
        //删除指定节点
        if(head == tail) {
            delete head;
            head = nullptr;
            tail = nullptr;
        } else if(p == head) {
            //头节点被删除
            head->next->prev = nullptr;
            head = head->next;
        } else if(p == tail) {
            p->prev->next = nullptr;
            tail = p->prev;
        } else {
            p->prev->next = p->next;
            p->next->prev = p->prev;
        }
    }
    void setHead(Node* p) {
        //将节点设置为头节点
        if(head == nullptr) {
            head = p;
            tail = p;
            p->next = p;
            p->prev = p;
        } else {
            p->next = head;
            head->prev = p;
            head = p;
        }
    }
    void deleteTail() {
        //删除尾部节点
        if(head == tail) {
            mp.erase(tail->key);
            delete tail;
            head = nullptr;
            tail = nullptr;
        } else {
            Node* p = tail;
            tail = tail->prev;
            tail->next = nullptr;
            mp.erase(p->key);
            delete p;
        }
    }
    void set(int k, int v) {
        if(mp.find(k) != mp.end()) {
            //找到时，删除该节点并插入到头部
            mp[k]->key = k;
            mp[k]->val = v;
            deleteNode(mp[k]);
            setHead(mp[k]);
        } else {
            //找不到时，创建节点并插入到头部
            Node* res = new Node(k, v);
            mp[k] = res;
            setHead(res);
            ++size;
            //大小超过容量限制时删除尾部节点
            if(size > cap) {
                deleteTail();
            }
        }
    }

    int get(int k) {
        if(mp.find(k) == mp.end()) {
            return -1;//不存在
        } else {
            //删除节点并添加到头部
            deleteNode(mp[k]);
            setHead(mp[k]);
            return mp[k]->val;
        }
    }

    vector<int> LRU(vector<vector<int> >& operators, int k) {
        cap = k;//设置容量
        size = 0;
        vector<int> ans;
        for(vector<int>& it : operators) {
            if(it[0] == 1) {
                set(it[1], it[2]);
            } else {
                ans.push_back(get(it[1]));
            }
        }
        return ans;
    }
};

复杂度分析：

时间复杂度：对于 和 操作，时间复杂度都是
空间复杂度：，因为哈希表和双向链表最多存储个元素。

方法二：增加虚拟节点

核心思想：

在双向链表的实现中，使用一个伪头部和伪尾部标记界限，这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在,可以减少很多if判断
图示：

核心代码：

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

class Solution {
private:
    unordered_map<int, Node*> mp;//用于快速查找键值对
    Node* head = nullptr;//伪头部
    Node* tail = nullptr;//伪尾部
    int cap;//容量
    int size;//当前大小
public:
    void deleteNode(Node* p) {
        //删除指定节点
        p->prev->next = p->next;
        p->next->prev = p->prev;
    }
    void setHead(Node* p) {
        //将节点设置为头节点
        p->next = head->next;
        head->next->prev = p;
        head->next = p;
        p->prev = head;
    }
    void deleteTail() {
        //删除尾部节点
        Node* p = tail->prev;
        if(p == head) {
            return;
        }
        tail->prev = p->prev;
        p->prev->next = tail;
        mp.erase(p->key);
        delete p;
    }
    void set(int k, int v) {
        if(mp.find(k) != mp.end()) {
            //找到时，删除该节点并插入到头部
            mp[k]->key = k;
            mp[k]->val = v;
            deleteNode(mp[k]);
            setHead(mp[k]);
        } else {
            //找不到时，创建节点并插入到头部
            Node* res = new Node(k, v);
            mp[k] = res;
            setHead(res);
            ++size;
            //大小超过容量限制时删除尾部节点
            if(size > cap) {
                deleteTail();
            }
        }
    }

    int get(int k) {
        if(mp.find(k) == mp.end()) {
            return -1;//不存在
        } else {
            //删除节点并添加到头部
            deleteNode(mp[k]);
            setHead(mp[k]);
            return mp[k]->val;
        }
    }

    vector<int> LRU(vector<vector<int> >& operators, int k) {
        cap = k;//设置容量
        size = 0;
        vector<int> ans;
        head = new Node(0, 0);
        tail = new Node(0, 0);
        //串联虚拟节点
        head->next = tail;
        tail->prev = head;
        for(vector<int>& it : operators) {
            if(it[0] == 1) {
                set(it[1], it[2]);
            } else {
                ans.push_back(get(it[1]));
            }
        }
        return ans;
    }
};

复杂度分析：

时间复杂度：对于 和 操作，时间复杂度都是
空间复杂度：，因为哈希表和双向链表最多存储 个元素。