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

设计LRU缓存结构

http://www.nowcoder.com/practice/e3769a5f49894d49b871c09cadd13a61

include

include

include

class Solution {
public:
/**
* lru design
* @param operators int整型vector<vector<>> the ops
* @param k int整型 the k
* @return int整型vector
*/
private:
list<pair<int ,int>> getList;
unordered_map<int, list<pair<int ,int>>::iterator> setList;
int capacity;
public:
void set(int key,int value)
{
auto iter= setList.find(key);
if( iter != setList.end())
{
getList.erase(setList[key]);
getList.push_front({key,value});
setList[key] = getList.begin();
}
else
{
if(getList.size() == capacity)
{
auto iter = setList.find(getList.back().first);
setList.erase(iter);
getList.pop_back();
}
getList.push_front({key,value});
setList[key] = getList.begin();
}
}
int get(int key)
{

    if(setList.find(key) != setList.end())
    {
        auto iter = setList[key];
        getList.push_front(*iter);
        setList[key] = getList.begin();
        getList.erase(iter);
        return setList[key] ->second;
    }
    else
    {
        return -1;
    }
}
vector<int> LRU(vector<vector<int> >& operators, int k) {
    // write code here
    vector<int> temp;
    if(k==0) return temp;
    capacity = k;
    for(int i=0; i< operators.size();i++)
    {
        if(operators[i][0] == 1)
        {
            if(operators[i][1] < (-2*pow(10,9)) || operators[i][1] > (2*pow(10,9))) continue;
            if(operators[i][2] < (-2*pow(10,9)) || operators[i][2] > (2*pow(10,9))) continue;
            set(operators[i][1],operators[i][2]);
        }
        else if(operators[i][0] == 2)
        {
            temp.push_back(get(operators[i][1]));
        }

    }
    return temp;
}

};

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 11:30
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务