题解 | #反转链表#

根据官方题解：建立双向链表和哈希表

class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    typedef pair<int, int> PII;
    list<PII> plist; // 存储查询表
    int capacity; // 容量
    unordered_map<int, list<PII>::iterator> mp; // 用于查询操作,映射查询表中的节点在查询表中的位置
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        vector<int> res;
        capacity = k;
        for(int i = 0; i < operators.size(); i++){
            if(operators[i][0] == 1){
                int key = operators[i][1], value = operators[i][2];
                set(key, value);
            }else{
                int key = operators[i][1];
                int x = get(key);
                res.push_back(x);
            }
        }
        return res;
    }

    void set(int key, int value){
        auto iter = mp.find(key);
        if(iter != mp.end()){
            plist.erase(mp[key]);
            plist.push_front({key, value});
            mp[key] = plist.begin(); // 建立映射
        }else{
            if(plist.size() == capacity){
                mp.erase(plist.back().first);// 抹去链表最后的数在map中的映射
                plist.pop_back();
            }
            plist.push_front({key, value});
            mp[key] = plist.begin();
        }
    }
    int get(int key){
        auto iter = mp.find(key);
        if(iter != mp.end()){
            plist.erase(mp[key]);
            plist.push_front({key, iter->second->second});
            mp[key] = plist.begin();
            return iter->second->second;
        }else{
            return -1;
        }
    }
};