设计LRU缓存结构

C++ 解法, 执行用时: 80ms, 内存消耗: 20780KB, 提交时间: 2022-07-05

static const auto io_sync_off = []()//lambda函数
{
    // turn off sync，关闭输入输出流的缓存
    std::ios::sync_with_stdio(false);
    // untie in/out streams，实现输入和输出流的解绑
    std::cin.tie(nullptr);
    return nullptr;
}();
class Solution {
    list<pair<int, int>> dlist;//双向链表
    unordered_map<int, list<pair<int, int>>::iterator> map;
    int cap;
    
    //用链表存，链表头部是最近使用的，尾部是最后使用的，如果要删去，就直接把尾部删去就好
public:
    Solution(int capacity){
         cap=capacity;
    }
    
    //key就变得最常用了
    int get(int key) {
        if(map.count(key))
        {
            //把这个放在头部，所以需要个tmp存着，然后删掉这个位置，再放到头部
            auto tmp=*map[key];
            dlist.erase(map[key]);
            //map.erase(key);
            dlist.push_front(tmp);//把它放在最前面
            map[key]=dlist.begin();
            //return tmp.second;
            return dlist.front().second;
        }
        return -1;
    }
    
    void set(int key, int value){
         if(map.count(key))//如果存在
         {
             dlist.erase(map[key]);//放在头部
             //map.erase(key);
         }
        else if(cap==dlist.size())
        {
            //先删掉末尾的
            auto tmp=dlist.back();
            map.erase(tmp.first);
            dlist.pop_back();
        }
        dlist.push_front(pair<int, int>(key, value));
        map[key]=dlist.begin();//第一个迭代器
    }
};

C++ 解法, 执行用时: 81ms, 内存消耗: 18480KB, 提交时间: 2022-06-19

static const auto __ = [] {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();
class Solution {
  public:
    Solution(int capacity) {
        // write code here
        capacity_ = capacity;
    }

    int get(int key) {
        // write code here
        const auto &node = map_.find(key);
        if (node == map_.end()) {
            return -1;
        }
        cache_.splice(cache_.begin(), cache_, node->second);
        return node->second->second;
    }

    void set(int key, int value) {
        // write code here
        const auto &node = map_.find(key);
        if (node != map_.end()) {
            node->second->second = value;
            cache_.splice(cache_.begin(), cache_, node->second);
            return;
        }
        if (cache_.size() == capacity_) {
            const auto &node = cache_.back();
            map_.erase(node.first);
            cache_.pop_back();
        }
        cache_.push_front(make_pair(key, value));
        map_[key] = cache_.begin();
    }

  private:
    int capacity_;
    list<pair<int, int>> cache_;
    unordered_map<int, list<pair<int, int>>::iterator> map_;
};

C++ 解法, 执行用时: 91ms, 内存消耗: 18452KB, 提交时间: 2022-04-28

static const auto __ = [] {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    Solution(int capacity){
        capacity_ = capacity;
    }
    
    int get(int key) {
        const auto& node = map_.find(key);
        if(node == map_.end())
            return -1;
        cache_.splice(cache_.begin(), cache_, node->second);
        return node->second->second;
    }
    
    void set(int key, int value){
        const auto& node = map_.find(key);
        if(node != map_.end()){
            node->second->second = value;
            cache_.splice(cache_.begin(), cache_, node->second);
            return ;
        }
        if(cache_.size()==capacity_){
            const auto& node = cache_.back();
            map_.erase(node.first);
            cache_.pop_back();
        }
        cache_.push_front(make_pair(key, value));
        map_[key] = cache_.begin();
    }
    
private:
    int capacity_;
    list<pair<int, int>> cache_;
    unordered_map<int, list<pair<int, int>>::iterator> map_;
};

C++ 解法, 执行用时: 92ms, 内存消耗: 18448KB, 提交时间: 2022-06-17

static const auto __ = [] {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    int num_max;
    unordered_map<int, pair<int, int>> m;
    queue<int> que;
    Solution(int capacity){
         // write code here
        num_max = capacity;
    }
    
    int get(int key) {
         // write code here
        if(m.count(key)){
            que.push(key);
            m[key].second++;
            return m[key].first;
        }
        else
            return -1;
    }
    
    void set(int key, int value){
         // write code here
        que.push(key);
        if(m.count(key)){
            m[key].first = value;
            m[key].second ++;
        }
        else{
            if(num_max>0)
                num_max--;
            else{
                int tem;
                while(1){
                    tem = que.front();
                    que.pop();
                    if(m[tem].second==1){
                        m.erase(tem);
                        break;
                    }
                    m[tem].second--;
                }
            }
            m.insert(make_pair(key, pair<int, int>(value, 1)));
        }
        
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* solution = new Solution(capacity);
 * int output = solution->get(key);
 * solution->set(key,value);
 */

C++ 解法, 执行用时: 93ms, 内存消耗: 18536KB, 提交时间: 2022-06-09

static const auto __ = [] {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();
class Solution {
  public:
    Solution(int capacity) {
        // write code here
        capacity_ = capacity;
    }

    int get(int key) {
        // write code here
        const auto& node = map_.find(key);
        if (node == map_.end()){
            return -1;
        }
        cache_.splice(cache_.begin(), cache_, node->second);
        return node->second->second;
    }

    void set(int key, int value) {
        // write code here
        const auto& node = map_.find(key);
        if (node!= map_.end()){
            node->second->second = value;
            cache_.splice(cache_.begin(), cache_, node->second);
            return;
        }
        if (cache_.size() == capacity_){
            const auto& node = cache_.back();
            map_.erase(node.first);
            cache_.pop_back();
        }
        cache_.push_front(make_pair(key, value));
        map_[key] = cache_.begin();
    }

  private:
    int capacity_;
    list<pair<int, int>> cache_;
    unordered_map<int, list<pair<int, int>>::iterator> map_;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* solution = new Solution(capacity);
 * int output = solution->get(key);
 * solution->set(key,value);
 */

详情