注意几点: 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; } };