哈希查,链表删,删的快查的快

设计LRU缓存结构

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

#include <unordered_map>
#include <iterator>

class Solution {
public:

    vector<int> LRU(vector<vector<int> >& operators, int k) 
    {
        vector<int> result;
        if (operators.empty() || k <= 0) {
            return result;
        }

        cap = k;

        for (auto c : operators) {
            if (c[0] == 1) {
                set(c[1], c[2]);
            } else {
                int val = get(c[1]);
                result.push_back(val);
            }
        }

        return result;
    }

    int get(int key)
    {
        auto iter = smap.find(key);
        if (iter == smap.end()) {
            return -1;
        }

        auto val =iter->second->second;
        slist.push_front({key,val});
        slist.erase(iter->second);
        smap[key] = slist.begin();

        return val;
    }

    void set(int key, int val) 
    {
        auto iter = smap.find(key);
        if (iter != smap.end()) {
            slist.erase(iter->second);
        }

        slist.push_front({key, val});
        smap[key] = slist.begin();

        if (slist.size() > cap) {
            smap.erase(slist.back().first);
            slist.pop_back();
        }

    }
    private:
    int cap;
    unordered_map<int, list<pair<int,int>>::iterator> smap;
    list<pair<int,int>> slist;
};
全部评论
为什么get里面要smap[key] = slist.begin();?
点赞 回复 分享
发布于 2021-09-17 01:00
查不是也要更新排序么
点赞 回复 分享
发布于 2021-06-06 17:06

相关推荐

不愿透露姓名的神秘牛友
07-24 13:40
点赞 评论 收藏
分享
06-25 09:33
厦门大学 Java
球球别拷打俺了:现在日常估计没啥hc了,等到八月多估计就慢慢有了。双九✌🏻不用焦虑的
投递快手等公司10个岗位
点赞 评论 收藏
分享
06-02 15:17
门头沟学院 Java
心爱的idea:怎么会呢 应该是打招呼有问题 问就说实习6个月全国可飞随时到岗
点赞 评论 收藏
分享
评论
13
1
分享

创作者周榜

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