题解 | #设计LRU缓存结构#

/*
    整体思路：
        unordered_map存储key，val键值对
        创建链表，新添加的或者是使用过的，尾插法插入链表末尾
        如果缓冲容量满了，直接删除链头元素就行，他就是最久未被使用的元素
        为了方便，添加了一个头节点；同时需要一个尾指针，方便插入链表尾部
*/


class Solution {
  public:
    class Node {
      public:
        int data;
        Node* next;
        Node(int data, Node* next) {
            this->data = data;
            this->next = next;
        }
    };
    int len;
    int cnt = 0;
    unordered_map<int, int> map;
    Node* dummy = new Node(-1, nullptr);
    Node* tail = dummy;
    Solution(int capacity) {
        len = capacity;
    }

    int get(int key) {
        if (map.find(key) == map.end())
            return -1;
        Node* p = dummy;
        while (p && p->next->data != key) {
            p = p->next;
        }
        Node* q = p->next;
        if(!q->next)
            return map[key];
        p->next = q->next;
        tail->next = q;
        q->next = nullptr;
        tail = q;
        return map[key];
    }

    void set(int key, int value) {
        if (map.find(key) != map.end()) {
            map[key] = value;
            Node* p = dummy;
            while (p && p->next->data != key) {
                p = p->next;
            }
            
            Node* q = p->next;
            if(!q->next)
                return;
            p->next = q->next;
            tail->next = q;
            q->next = nullptr;
            tail = q;
        } else {
            if (cnt == len) {
                int del = dummy->next->data;
                auto it = map.find(del);
                map.erase(it);
                Node* p = dummy->next;
                dummy->next = p->next;
                delete p;
                p = new Node(key, nullptr);
                tail->next = p;
                tail = p;
                map[key] = value;
            }else{
                map[key] = value;
                cnt++;
                Node*p = new Node(key, nullptr);
                tail->next = p;
                tail = p;
            }
        }
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* solution = new Solution(capacity);
 * int output = solution->get(key);
 * solution->set(key,value);
 */