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

今天终于把101刷完了

不刷了，就重复刷这些题就好了。

接下来的时间要打好基础和项目。

class Solution {
  public:
    /**
     * lfu design
     * @param operators int整型vector<vector<>> ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> LFU(vector<vector<int> >& operators, int k) {
      capacity = k;
      std::vector<int> res;
      
      for (int i = 0; i < operators.size(); ++i) {
        if (operators[i][0] == 1) {
          set(operators[i][1], operators[i][2]);
        } else {
          res.push_back(get(operators[i][1]));
        }
      }
      
      return res;
    }
  
    int get(int key) {
      int res = -1;
      if (key_mp.count(key)) {
        res = (*key_mp[key])[2];
        update(key_mp[key], key, res);
      }
      return res;
    }
   
    void set(int key, int value) {
      if (key_mp.count(key)) {
        update(key_mp[key], key, value);
      } else {
        if (capacity <= 0) {
          int old_key = freq_mp[min_freq].back()[1];
          freq_mp[min_freq].pop_back();
          if (freq_mp[min_freq].empty()) {
            freq_mp.erase(min_freq);
          }
          key_mp.erase(old_key);
        } else {
          --capacity;
        }
        min_freq = 1;
        freq_mp[min_freq].push_front({1, key, value});
        key_mp[key] = freq_mp[min_freq].begin();
      }
    }
  
    void update(std::list<std::vector<int>>::iterator it, const int &key, const int &value) {
      int freq = (*it)[0];
      freq_mp[freq].erase(it);
      if (freq_mp[freq].empty()) {
        freq_mp.erase(freq);
        if (freq == min_freq) {
          ++min_freq;
        }
      }
      freq_mp[freq + 1].push_front({freq + 1, key, value});
      key_mp[key] = freq_mp[freq + 1].begin();
    }
  
  private:
    int capacity;
    int min_freq;
    std::unordered_map<int, std::list<std::vector<int>>> freq_mp;
    std::unordered_map<int, std::list<std::vector<int>>::iterator> key_mp;
};