LRU缓存机制

#include <unordered_map>

struct DListNode{
    int key, val;
    DListNode* pre;
    DListNode* next;
    DListNode(int k, int v): key(k), val(v), pre(nullptr), next(nullptr){};
};


class Solution {
private:
    int size = 0;
    DListNode* head;
    DListNode* tail;
    unordered_map<int, DListNode*> mp;

public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        // write code here
        if(k < 1) return {};
        this->size = k;
        this->head = new DListNode(0,0);
        this->tail = new DListNode(0,0);
        this->head->next = this->tail;
        this->tail->pre = this->head;

        if(operators.size() == 0) return {};

        vector<int> res;

        for(vector<int> op : operators){
            if(op[0] == 1) {
                set(op[1], op[2]);
            }
            else if(op[0] == 2){
                int value = get(op[1]);
                res.push_back(value);
            }
        }
        return res;
    }

    void set(int key, int val){
        if(mp.find(key) == mp.end()){ // hashmap 中没找到
            DListNode* node = new DListNode(key, val);
            mp[key] = node;
            if(this->size <= 0){
                removeLast();
            }
            else{
                this->size--;
            }
            insertFirst(node);
        }
        else{  // hashmap 中已经有了,也就是链表里也已经有了
            mp[key]->val = val;
            moveToHead(mp[key]);
        }
    }


    int get(int key){
        int ret = -1;
        if(mp.find(key) != mp.end()){
            ret = mp[key]->val;
            moveToHead(mp[key]);
        }
        return ret;
    }

    void moveToHead(DListNode* node){
        if(node->pre == this->head) return;
        node->pre->next = node->next;
        node->next->pre = node->pre;
        insertFirst(node);
    }


    void removeLast(){
        mp.erase(this->tail->pre->key);
        this->tail->pre->pre->next = this->tail; // remove the last node in dlist
        this->tail->pre = this->tail->pre->pre;
    }

    void insertFirst(DListNode* node){
        node->pre = this->head;
        node->next = this->head->next;
        this->head->next->pre = node;
        this->head->next = node;
    }

};

开始初始化一个head节点与一个tail节点,方便以后插入节点和删除节点,中间放置操作的节点。
全部评论

相关推荐

测试糕手手:社会第一课,随便吹牛逼,直接说四个月,别老实。老实人只会被欺负
点赞 评论 收藏
分享
就前几天旅游的时候,打开抖音就经常刷到这类视频:以前是高学历学生、老师、主持人,现在做着团播、擦边主播的工作,以及那些经过精心包装的“职业转型”故事——从铺天盖地的VLOG到所谓的“04年夜场工作日记”,这些内容在初中升学、高考放榜等关键时间节点持续发酵。可以说非常直接且精准地在潜移默化地影响着心智尚未成熟的青少年,使其对特殊行业逐渐脱敏。那我就想问了:某些传播公司、平台运营者甚至某些夜场的老板,你们究竟在传递怎样的价值观?点开那些视频,评论区里也是呈现明显的两极分化:一种是​​经济下行论​​:“现在就业市场已经艰难到这种程度了吗?”​​一种是事实反驳派​​:这些创作者往往拥有名校背景,从事着...
牛客刘北:被环境教育的,为了能拿到足够的钱养活自己,不甘心也得甘心,现在的短视频传播的思想的确很扭曲,但是很明显,互联网玩上一年你就能全款提A6,但你全心全意不吃不喝工作一年未必能提A6,但是在高考中考出现这个的确很扭曲,在向大家传播“不上学,玩互联网也可以轻松年入百万”,不是人变了,是社会在变
预测一下26届秋招形势
点赞 评论 收藏
分享
Twilight_m...:经典我朋友XXXX起手,这是那种经典的不知道目前行情搁那儿胡编乱造瞎指导的中年人,不用理这种**
点赞 评论 收藏
分享
06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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