题解 | #牛群缓存系统#

#include <vector>
class DoubleMap {

  public:
    map<int, int> kToV;
    map<int, int> vToK;
    void addKV(int key, int value) {
        if (kToV.count(key)) erase(key);
        kToV[key] = value;
        vToK[value] = key;
    }
    void erase(int key) {
        int value = kToV[key];
        vToK.erase(value);
        kToV.erase(key);
    }

    // 返回 value 最大的 key
    int GetKeyOfMinValue() {
        return vToK.begin()->second;
    }
};

class CowManagement {
  private:
    int time;
    int capacity;
    map<int, int> cowToAge;
    DoubleMap cowToTime; // 牛被访问的时间

    // 删除时间最久的
    void LRU() {
        int key = cowToTime.GetKeyOfMinValue();
        cowToTime.erase(key);
        cowToAge.erase(key);
    }

    // 更新 key 的访问时间
    void UpdateTime(int key) {
        ++time;
        cowToTime.addKV(key, time);
    }


  public:
    CowManagement(int capacity): capacity(capacity) {};

    int get(int key) {
        if (!cowToAge.count(key)) return -1;
        UpdateTime(key); // 记录新的访问时间
        return cowToAge[key];
    }

    void put(int key, int value) {
        // 添加新的键值对
        cowToAge[key] = value;
        UpdateTime(key);
        // 如果满了，那么 LRU
        if (cowToAge.size() > capacity) LRU();
    }

};


class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param operations int整型vector<vector<>>
     * @param values int整型vector<vector<>>
     * @return int整型vector
     */
    vector<int> cow_management_system(vector<vector<int> >& operations,
                                      vector<vector<int> >& values) {
        // write code here
        CowManagement cows(values[0][0]);
        int valueIt = 0;
        for (auto& op : operations) {
            if (op[0] == 0) continue;
            else if (op[0] == 1) { // put
                vector<int>& kv = values[++valueIt];
                cows.put(kv[0], kv[1]);
            } else if (op[0] == 2) { // get
                ans.push_back(cows.get(values[++valueIt][0]));
            }
        }

        return ans;
    }
    vector<int> ans;
};

双map