设计类的题一直是我的痛点。。。
参考了一下labuladong的题解
class LRUCache {
private:int cap;// 双链表：装着 (key, value) 元组list<pair<int, int>> cache;// 哈希表：key 映射到 (key, value) 在 cache 中的位置unordered_map<int, list<pair<int, int>>::iterator> map;
public:LRUCache(int capacity) {this->cap = capacity; }int get(int key) {auto it = map.find(key);// 访问的 key 不存在if (it == map.end()) return -1;// key 存在，把 (k, v) 换到队头pair<int, int> kv = *map[key];cache.erase(map[key]);cache.push_front(kv);// 更新 (key, value) 在 cache 中的位置map[key] = cache.begin();return kv.second; // value}void put(int key, int value) {/* 要先判断 key 是否已经存在 */ auto it = map.find(key);if (it == map.end()) {/* key 不存在，判断 cache 是否已满 */ if (cache.size() == cap) {// cache 已满，删除尾部的键值对腾位置// cache 和 map 中的数据都要删除auto lastPair = cache.back();int lastKey = lastPair.first;map.erase(lastKey);cache.pop_back();}// cache 没满，可以直接添加cache.push_front(make_pair(key, value));map[key] = cache.begin();} else {/* key 存在，更改 value 并换到队头 */cache.erase(map[key]);cache.push_front(make_pair(key, value));map[key] = cache.begin();}}
};