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

#include <any>
#include <unordered_map>
class Solution {
public:
    deque<int> dequeValue; // 用于保存顺序
    unordered_map<int, int> hashValue;
    int cap;
    Solution(int capacity){
    // write code here
    // 使用堆栈的方式，哈希表的方法
        cap = capacity;
    }

    int get(int key) {
    // write code here
        if(hashValue.find(key)!=hashValue.end()){
            dequeValue.erase(find(dequeValue.begin(), dequeValue.end(), key));
            dequeValue.push_back(key);
            // swap(* find(dequeValue.begin(), dequeValue.end(), key), *dequeValue.end());
            // cout<<"查询：";
            // for(auto i : dequeValue) cout<<i<<","; cout<<endl;
            return hashValue[key];
        }
        else{
            return -1;
        }
    }

    void set(int key, int value){
    // write code here
        if(hashValue.find(key)!=hashValue.end()){
            hashValue[key] = value; //赋值
            dequeValue.erase(find(dequeValue.begin(), dequeValue.end(), key));
            dequeValue.push_back(key);
            //swap(* find(dequeValue.begin(), dequeValue.end(), key), *dequeValue.end());
            // cout<<"赋值：";
            // for(auto i : dequeValue) cout<<i<<","; cout<<endl;
        }
        else{
            hashValue[key] = value; //赋值
            dequeValue.push_back(key);
            
            if(hashValue.size()>cap){
                int dropKey = dequeValue.front();
                dequeValue.erase(dequeValue.begin()); //删除
                hashValue.erase(dropKey);// 删除
                cout<<"删除了"<<dropKey<<endl;
            }
            // cout<<"赋值：";
            // for(auto i : dequeValue) cout<<i<<","; cout<<endl;
        }
    }
};

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