146. LRU Cache

解題思路

看 neetcode 的影片，用他的解法來解。

改天自己重新思考重寫一次。

程式碼

class Node {
public:
    int key, value;
    Node *prev, *next;
    Node(int key, int value) {
        this->key = key;
        this->value = value;
        this->prev = this->next = nullptr;
    }
};

class LRUCache {
public:
    int cap;
    unordered_map<int, Node*> cache; // key to node pointer
    Node *left, *right; // least recent, most recent

    LRUCache(int capacity) {
        this->cap = capacity;
        this->left = new Node(0, 0);
        this->right = new Node(0, 0);
        this->left->next = this->right;
        this->right->prev = this->left;
    }

    void remove(Node* node) { // remove node from double linked-list
        Node *pre = node->prev, *nxt = node->next;
        pre->next = nxt;
        nxt->prev = pre;
    }

    void insert(Node* node) { // insert node into double linked-list
        Node *pre = this->right->prev, *nxt = this->right;
        pre->next = nxt->prev = node;
        node->prev = pre;
        node->next = nxt;
    }
    
    int get(int key) {
        if(cache.count(key)) { // first update the node to the right-most
            remove(cache[key]);
            insert(cache[key]);
            return cache[key]->value;
        }
        return -1;
    }
    
    void put(int key, int value) {
        if(cache.count(key))
        {
            remove(cache[key]);
        }
        cache[key] = new Node(key, value); // update hashmap
        insert(cache[key]); // update linked-list

        if(cache.size() > this->cap)
        {
            Node* LRU = this->left->next;
            remove(LRU); // remove the LRU 
            cache.erase(LRU->key);
        }
    }
};