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

注意几点：
1. 缓存长度在上层修改，不要在底层函数修改！！
2. 注意同步维护 umap和doubleList ;
class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    struct Node {
        Node(int k, int v): key(k), val(v) {
            prev = nullptr;
            next = nullptr;
        }
        int key, val;
        Node *prev, *next;

    };
    class DoubleList {
public:
            DoubleList(int k) {
                cap = k;
                first = new Node(0, 0);
                last = new Node(0, 0);
                first->next = last;
                first->prev = nullptr;
                last->prev = first;
                last->next = nullptr;
            }
        ~DoubleList () {
            delete(first);
            delete(last);
        }
            int get(int key) {
                if ( umap.count(key ) == 0 ) return -1;
                int res = umap[key]->val;
                moveToLast(umap[key]);
                return res;
            }
            void set(int key, int value) {
                if ( umap.count( key ) != 0 ) {
                    umap[key]->val = value;
                    moveToLast(umap[key]);
                    return;
                }
                if ( len >= cap ) {
                    int rk = removeFirst();
                    umap.erase(rk);
                    --len;
                }
                Node *node = new Node(key, value);
                umap[key] = node;
                addLast(node);
                ++len;
            }
    private:
            unordered_map<int, Node *> umap;
            int cap, len;
        Node *last, *first;
        void addLast(Node *node) {
            if ( !node ) return;
            last->prev->next = node;
            node->prev = last->prev;
            node->next = last;
            last->prev = node;
            // ++len;
        }
        int remove(Node *n) {
            n->prev->next = n->next;
            n->next->prev = n->prev;
            int rk = n->key;
            delete(n);
            return rk;
            //--len;
        }
        int removeFirst()
        {
            // if ( len <= 0 ) return;
            return remove(first->next);
        }
        void moveToLast(Node *n) {
            if ( n->next == last ) {
                return;
            }
            n->prev->next = n->next;
            n->next->prev = n->prev;
            addLast(n);
        }
    };
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        // write code here
        vector<int> res;
        DoubleList dl = DoubleList(k);
        for (int i=0;i<operators.size(); ++i) {
            if(operators[i][0] == 1) {
                dl.set(operators[i][1], operators[i][2]);
            } else if ( operators[i][0] == 2 ) {
                res.push_back( dl.get( operators[i][1] ) );
            }
        }
        return res;
    }
};