题解 | #设计LRU缓存结构#
设计LRU缓存结构
http://www.nowcoder.com/practice/e3769a5f49894d49b871c09cadd13a61
class Solution { public: /** * lru design * @param operators int整型vector<vector<>> the ops * @param k int整型 the k * @return int整型vector */ typedef struct KeyValue { int nKey; int nValue; }KeyValue; vector<KeyValue> vecCache; int GetCache(int nKey) { for(int i=0;i<vecCache.size();i++) { if(nKey == vecCache[i].nKey) { int nRet = vecCache[i].nValue; if(i != vecCache.size()-1) { KeyValue tmp = vecCache[i]; for(int j=i;j<vecCache.size();j++) { vecCache[j] = vecCache[j+1]; } vecCache[vecCache.size()-1] = tmp; } return nRet; } } return -1; } void InsertCache(KeyValue keyValue, int k) { if(vecCache.size() > 0 && vecCache.size() >= k) { vecCache.erase(vecCache.begin()); } for(int i=0;i<vecCache.size();i++) { if(keyValue.nKey == vecCache[i].nKey) { vecCache[i].nValue = keyValue.nValue; return; } } vecCache.push_back(keyValue); } vector<int> LRU(vector<vector<int> >& operators, int k) { vector<int> vecRet; // write code here for(int i=0;i<operators.size();i++) { vector<int> & one_operator = operators[i]; int nType = one_operator[0]; if(nType == 1) { int nKey = one_operator[1]; int nValue = one_operator[2]; KeyValue tmpKeyValue; tmpKeyValue.nKey = nKey; tmpKeyValue.nValue = nValue; InsertCache(tmpKeyValue,k); } else if(nType == 2) { int nKey = one_operator[1]; vecRet.push_back(GetCache(nKey)); } else { continue; } } return vecRet; } };