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

设计LRU缓存结构

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

class Solution {
public:
    struct Node
    {
        int key,val;
        Node *left,*right;
        Node(int _key,int _val):key(_key),val(_val),left(NULL),right(NULL){}
    }*L,*R;
    Solution(){ //初始化
        L=new Node(-1,-1);
        R=new Node(-1,-1);
        L->right=R;
        R->left=L;
    }
    vector<int>res;
    unordered_map<int,Node*>hash;//哈希表来快速查找
    int n;//总容量
    void insert(Node *p)//插入一页
    {
        p->right=L->right;
        L->right->left=p;
        L->right=p;
        p->left=L;
    }
    void remove(Node *p)//删除
    {
        p->left->right=p->right;
        p->right->left=p->left;
    }
    void get(int key)
    {
        if(hash.count(key)==0)
        {
            res.push_back(-1);
            return;
        }
        auto p=hash[key];
        remove(p);
        insert(p);
        res.push_back(p->val);
    }
    void set(int key,int value)
    {
        //如果有了,那就修改值
        if(hash.count(key))
        {
            auto p=hash[key];
            p->val=value;
            remove(p);
            insert(p);
        }
        else    //没有,看满没满
        {
            if(n==hash.size())
            {
                auto p=R->left;
                remove(p);
                hash.erase(p->key);//重点
                delete p;
            }
                auto p=new Node(key,value);
                hash[key]=p;
                insert(p);
        }

    }
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        // write code here
        n=k;
        for(int i=0;i<operators.size();i++)
        {
            if(operators[i][0]==1)
                set(operators[i][1],operators[i][2]);
            else 
                get(operators[i][1]);
        }
        return res;
    }
};
全部评论

相关推荐

门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
给我发了笔试链接,想着等晚上回去做,结果还没做流程就终止了
伟大的小黄鸭在学习:我猜就是笔试几乎没用,就是用来给用人部门拖时间复筛简历的,可能用人部门筛到你简历觉得不合适就提前挂了
投递小鹏汽车等公司10个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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