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

/* 解题思路(笔记)：

• 1 - 没有什么可以说的，用的是STL的list，key和value用pair<int, int>即可

• 2 - 有可以优化的地方，在set的时候，找到的时候就应该立刻删除，当时脑抽了，

• 没删，结果回头删又遍历了一趟

• /
  class Solution {
  public:
  /**

  • lru design

  • @param operators int整型vector<vector<>> the ops

  • @param k int整型 the k

  • @return int整型vector

  • /
    vector<int> LRU(vector<vector<int> >& operators, int k) {
    vector<int> res;
    res.clear();
    list<pair<int, int>> LRU;</int></int></int>

    for(vector<int>& opt : operators){</int>

      // set
      if(opt[0] == 1){
          int index = -1;
          // 找一下存不存在
          auto itr = LRU.begin();
          for(int i=0; i<LRU.size(); i++){
              if(opt[1] == itr->first){
                  index = i;
                  break;
              }
              itr++;
          }
          // 如果不存在的话
          if(index == -1){
              // 如果小于k的话
              if(LRU.size()<k)  LRU.push_front(pair<int, int>(opt[1], opt[2]));
              else{
                  LRU.push_front(pair<int, int>(opt[1], opt[2]));
                  LRU.pop_back();
              }
          // 如果存在的话
          }else{
              auto itr = LRU.begin();
              for(int i=0; i<=index; i++) itr++;
              LRU.erase(itr);
              LRU.push_front(pair<int, int>(opt[1], opt[2]));
          }
      // get
      }else if(opt[0] == 2){
           bool flag = false;
           for(auto itr = LRU.begin(); itr!=LRU.end(); itr++){
               if(itr->first == opt[1]){
                   flag = true;
                   res.push_back(itr->second);
                   LRU.push_front(pair<int, int>(itr->first, itr->second));
                   LRU.erase(itr);
                   break;
               }
           }
           if(!flag) res.push_back(-1);
      }

    }

    return res;
    }
    };