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

struct Node {
    int key;
    int val;
    Node *next;
    Node *pre;
    Node(): key(0), val(0), next(nullptr), pre(nullptr) {}
    Node(int _key, int _val): key(_key), val(_val), next(nullptr), pre(nullptr) {}
};

class Solution {
private:
    unordered_map<int, Node*> hashtable;
    int cap;
    int size;
    Node *head;
    Node *tail;
public:
    Solution(int capacity){
         // write code here
         // 第一处错误，多加了int
         // int cap = capacity;
         // int size = 0;
        cap = capacity;
        size = 0;
        // 第二处错误，忘记初始化head和tail
        head = new Node();
        tail = new Node();
        head->pre = nullptr;
        head->next = tail;
        tail->pre = head;
        tail->next  = nullptr;
    }
    
    void AddToHead(Node *node) {
        node->pre = head;
        node->next = head->next;
        head->next = node;
        node->next->pre = node;
    }
    
    void MoveToHead(Node *node) {
        node->pre->next = node->next;
        node->next->pre = node->pre;
        AddToHead(node);
    }
    
    int get(int key) {
         // write code here
        if (hashtable.find(key) == hashtable.end()) return -1;
        if (hashtable[key]->pre == head) return hashtable[key]->val;
        MoveToHead(hashtable[key]);
        return hashtable[key]->val;
    }
    
    void set(int key, int value){
         // write code here
        if (hashtable.find(key) != hashtable.end()) {
            hashtable[key]->val = value;
            MoveToHead(hashtable[key]);
            // 第四处错误，return掉了
            return;
        }
        Node *node = new Node(key, value);
        hashtable[key] = node;
        AddToHead(node);
        size++;
        if (size <= cap) {
            return;
        } else {
            Node *remove_node = tail->pre;
            // 第三处错误，移错key了
            hashtable.erase(remove_node->key);
            remove_node->pre->next = tail;
            tail->pre = remove_node->pre;
            delete remove_node;
            size--;
        }
    }
};