LeetCode 146. LRU Cache 优化网上博客,C++极简代码


这题用C++ 博客( https://blog.csdn.net/qq508618 ... 95188 )的代码已经很好了,唯一不足是在insert的时候,已经超过
最大容量才会弹出元素,我简单优化了一下,在最大容量先弹出,再插入,AC。
class LRUCache{  
public:  
    LRUCache(int capacity){
        size = capacity;
    }  
    int get(int key){  
        auto it = hash.find(key);  
        if(it == hash.end()) return -1;  
        cache.splice(cache.begin(), cache, it->second);  
        return it->second->second;  
    }  
    void put(int key, int value){  
        auto it = hash.find(key); 
        if(it != hash.end()){
            it->second->second = value;
            return cache.splice(cache.begin(), cache, it->second);
        }
        if(cache.size() + 1 > size){  
            hash.erase(cache.back().first);  
            cache.pop_back();  
        }
        cache.insert(cache.begin(), make_pair(key, value));  
        hash[key] = cache.begin();  
    }  
private:  
    unordered_map<int, list<pair<int, int>>::iterator> hash;
    list<pair<int, int>> cache;
    int size;
};  
已邀请:

要回复问题请先登录注册

返回顶部