题解 | #牛群缓存系统#
牛群缓存系统
https://www.nowcoder.com/practice/19238acf953c47eb98f24340c8127f33
#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