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

#include <string>
#include <unordered_map>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param operators string字符串vector 
     * @param param int整型vector<vector<>> 
     * @param capacity int整型 
     * @return string字符串vector
     */
    vector<string> LRUCache(vector<string>& operators, vector<vector<int> >& param, int capacity) {
        // // write code here
        vector<string> res;
        // Solution s(capacity);
        // for(int i=0;i<operators.size();i++){
        //     if(operators[i]=="set"){
        //         string str=s.set(param[i][0],param[i][1]);
        //         res.push_back(str);
        //     }else if(operators[i]=="get"){
        //         string str=s.get(param[i][0]);
        //         res.push_back(str);
        //     }
        // }
        return res;
    }
    Solution(int capacity):_capacity(capacity){}; 
    int get(int key){
        auto it=_umap.find(key);
        if(it!=_umap.end()){
            _lru.splice(_lru.begin(),_lru,it->second);
            return it->second->second;
        }
        return -1;
    }
    void set(int key,int val){
        auto it=_umap.find(key);
        if(it !=_umap.end()){//_umap能找到信息
            _lru.splice(_lru.begin(), _lru,it->second);
            it->second->second=val;
            return ;
        }
        //_umap未找到信息 添加并判断是否需要删除
        _lru.emplace_front(key,val);
        _umap.emplace(key,_lru.begin());
        if(_umap.size()>_capacity){
            _umap.erase(_lru.back().first);
            _lru.pop_back();
        }
    }
private:
list<pair<int,int>> _lru;
unordered_map<int, list<pair<int,int>>::iterator> _umap;
int _capacity;
};