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

哈希+双链表组合实现

// class Solution {
//   public:
//     /**
//      * lru design
//      * @param operators int整型vector<vector<>> the ops
//      * @param k int整型 the k
//      * @return int整型vector
//      */
//     struct node {
//         int key_;
//         int val_;
//         node* pre_;
//         node* next_;
//         node(int key, int val)
//             : key_(key)
//             , val_(val)
//             , pre_(nullptr)
//             , next_(nullptr)
//         {}
//     };

//     void updata(node* Node, int val) {
//         //更新value的值。
//         Node->val_ = val;
//         //跟新优先级。
//         node* pre = Node->pre_;
//         pre->next_ = Node->next_;
//         Node->next_->pre_ = pre;
//         cout << "*" << endl;
//         Node->next_ = head->next_;
//         head->next_->pre_ = Node;
//         head->next_ = Node;
//         Node->pre_ = head;
//         cout << "*" << endl;

//     }

//     int set(int key, int val, int k) {

//         if (map_.count(key)) {
//             cout << 1111 << endl;
//             //  cout<<map_[key]->key_<<endl;
//             //updata(map_[key],val);
//         } else {
//             node* Node = new node(key, val);
//             map_[key] = Node;
//             //头插入。
//             Node->next_ = head->next_;
//             Node->next_->pre_ = Node;
//             head->next_ = Node;
//             Node->pre_ = head;

//             node* cur = head->next_;
//             //  while(cur->next_!=tail)
//             //  {
//             //  cout<<cur->key_<<cur->val_<<endl;
//             //  cur=cur->next_;
//             //  }
//             size_++;
//             if (size_ > k) {
//                 node* Node = tail->pre_;
//                 node* pre = Node->pre_;
//                 pre->next_ = tail;
//                 tail->pre_ = pre;
//                 delete Node;
//                 map_.erase(Node->val_);

//                 //这样尾删是错的，不知咋回事，见鬼了。
//                 //  node* Node=tail->pre_;
//                 //  Node->pre_->next_=tail;
//                 //  tail->pre_=Node->pre_;
//                 //  map_.erase(Node->key_);
//                 //  delete Node;
//                 size_--;
//             }

//         }

//         return 9;
//     }
//     int get(int key) {
//         if (map_.count(key)) {
//             updata(map_[key], map_[key]->val_);
//             return map_[key]->val_;
//         }
//         return -1;
//     }
//     unordered_map<int, node*> map_;
//     node* head = new node(-1, -1);
//     node* tail = new node(-1, -1);
//     int size_;
//     vector<int> LRU(vector<vector<int> >& operators, int k) {
//         // write code here
//         size_ = k;
//         int n = operators.size();
//         vector<int> ans;
//         head->next_ = tail;
//         tail->pre_ = head;
//         for (int i = 0; i < n; i++) {
//             if (operators[i].size() == 3) {
//                 set(operators[i][1], operators[i][2], k);
//             } else {
//                 ans.push_back(get(operators[i][1]));
//             }
//         }
//         return ans;
//     }

// };


class Solution {
  public:
    struct node {//设置双向链表结构
        node* next;
        node* pre;
        int key;
        int val;
        node(int k, int v) : key(k), val(v), next(NULL), pre(NULL)
        {}//可以直接输⼊数字初始化};
    };
    node* head = new node(-1, -1);//设置⼀个头
    node* tail = new node(-1, -1);//设置⼀个尾
    int length = 0;//记录链表中有效结点（除去头尾）的数量
    map<int, node* > mp; //哈希表
    void update(node*p, int val_) {
        p->val=val_;
        node* q = p->pre;
        q->next = p->next;
        p->next->pre = q;

        p->next = head->next;
        head->next->pre = p;
        head->next = p;
        p->pre = head;
    }
    void set(int key, int val, int k) { //插⼊数据
        if (mp.count(key)) //插⼊的数据已经存在，更新p节点的位置
            update(mp[key], val);
        else { //否则加⼊数据
            node* p = new node(key, val); //创建新节点加⼊哈希表
            mp[key] = p;
            length++;
//将p节点插⼊到第⼀个位置
            p->next = head->next;
            p->next->pre = p;
            head->next = p;
            p->pre = head;
            if (length > k) { //超出LRU缓存空间
                node* q = tail->pre->pre;
                node* t = q->next;
                q->next = tail;
                tail->pre = q;
                mp.erase(t->key);//删除map⾥⾯的数据
                delete t;
            }
        }
    }
    int get(int key) { //访问数据
        if (mp.count(key)) { //哈希表找到数据更新节点，并返回
            node* p = mp[key];
            update(p,p->val);
            return p->val;
        } else { //返回-1
            node* p = new node(-1, -1);
            return p->val;
        }

    }
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        head->next = tail;
        tail->next = head; //先将链表⾸位相接,便于插⼊与删除
        vector<int> res; //记录输出
        for (int i = 0; i < operators.size(); i++) {
            if (operators[i][0] == 1)
                set(operators[i][1], operators[i][2], k);
            else if (operators[i][0] == 2) {
                res.push_back(get(operators[i][1]));
            }
        }
        return res;
    }
};