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

双向链表+哈希表，哈希表的目的是为了实现O(1)的时间复杂度。另外要注意的就是在set和get过程中要同时维护双向链表和哈希表。

class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    void set(int key,int value){
        auto iter=k_iter.find(key);
        if(iter!=k_iter.end()){
            kv_list.erase(k_iter[key]);
            kv_list.push_front({key,value});
            k_iter.insert({key,kv_list.begin()});
        }
        else{
            if(kv_list.size()>=capacity){
                k_iter.erase(kv_list.back().first);
                kv_list.pop_back();
            }
            kv_list.push_front({key,value});
            k_iter.insert({key,kv_list.begin()});
        }
    }
    
    int get(int key){
        int val{-1};
        auto iter=k_iter.find(key);
        if(iter==k_iter.end()){ //不存在
            return val;
        }
        else{ //存在
            val=iter->second->second;
            kv_list.erase(iter->second);
            kv_list.push_front({key,val});
            k_iter[key]=kv_list.begin();
        }
        return val;
    }
    
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        // write code here
        vector<int> result{};
        if(k==0){
            return result;
        }
        capacity=k;
        for(auto x : operators){
            if(x[0]==1){
                set(x[1],x[2]);
            }
            else{
                result.push_back(get(x[1]));
            }
        }
        return result;
    }
private:
    int capacity;
    list<pair<int,int>> kv_list;
    unordered_map<int,list<pair<int,int>>::iterator> k_iter; //保存key对应元素的位置
};