题解 | #设计LRU缓存结构# C++ 解法

题解 | #设计LRU缓存结构#
C++ 解法

class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    struct DLinkedNode {
        int key, val;
        DLinkedNode *prev, *next;
        DLinkedNode(): key(0), val(0), prev(nullptr), next(nullptr) {}
        DLinkedNode(int key, int val): key(key), val(val), prev(nullptr), next(nullptr) {}
    };
    class LRU_INIT {
    public:
        LRU_INIT(int capacity): size(0), capacity(capacity) {
            head = new DLinkedNode();
            tail = new DLinkedNode();
            head->next = tail;
            tail->prev = head;
        }
        int get(int key) {
            if (!cache.count(key)) {
                return -1;
            } else {
                DLinkedNode *node = cache[key];
                removeNode(node);
                addToHead(node);
                return node->val;
            }
            return -1;
        }
        void set(int key, int val) {
            if (!cache.count(key)) {
                DLinkedNode *node = new DLinkedNode(key, val);
                addToHead(node);
                ++size;
                cache.insert(make_pair(key, node));
                if (size > capacity) {
                    DLinkedNode *node = tail->prev;
                    removeNode(node);
                    --size;
                    cache.erase(node->key);
                    delete node;
                }
            } else {
                DLinkedNode *node = cache[key];
                node->val = val;
                removeNode(node);
                addToHead(node);
            }
            return ;
        }
    private:
        int size, capacity;
        DLinkedNode *head, *tail;
        unordered_map<int, DLinkedNode *> cache;
        void addToHead(DLinkedNode *node) {
            node->next = head->next;
            node->prev = head;
            head->next->prev = node;
            head->next = node;
            return ;
        }
        void removeNode(DLinkedNode *node) {
            node->prev->next = node->next;
            node->next->prev = node->prev;
            return ;
        }
    };
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        LRU_INIT lru(k);
        vector<int> ans;
        for (vector<int> &v : operators) {
            if (v[0] == 1) {
                lru.set(v[1], v[2]);
            } else if (v[0] == 2) {
                int t = lru.get(v[1]);
                ans.push_back(t);
            }
        }
        return ans;
    }
};