力扣 hot100 Day41

146. LRU 缓存

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

//自己写的shit
class LRUCache {
public:LRUCache(int capacity) {max = capacity;num = 0;}int get(int key) {if (record.count(key)) {order[key] = 0;incrementOtherKeys(key);return record[key];}return -1;}void put(int key, int value) {if (record.count(key)) {record[key] = value;order[key] = 0;incrementOtherKeys(key);} else {record[key] = value;order[key] = 0;incrementOtherKeys(key);num++;if (num > max) {int max_order_key = -1;int max_order_value = -1;for (const auto& pair : order) {if (pair.second > max_order_value) {max_order_value = pair.second;max_order_key = pair.first;}}if (max_order_key != -1) {record.erase(max_order_key);order.erase(max_order_key);num--;}}}}private:unordered_map<int, int> record;unordered_map<int, int> order; int num;int max;void incrementOtherKeys(int key) {for (auto& pair : order) {if (pair.first != key) {pair.second++;}}}
};

这个代码过不了测试，超时，不过逻辑应该没问题

主要卡时间的地方在于，每次操作都需要更改order哈希表，这种记录新旧顺序的方法很烂

最优方法是使用双向链表

//抄的
class LRUCache {
private:int capacity;list<pair<int, int>> cache; unordered_map<int, list<pair<int, int>>::iterator> record; // 哈希表：键 -> 链表节点public:LRUCache(int capacity) : capacity(capacity) {}int get(int key) {auto it = record.find(key);if (it == record.end()) return -1;// 将节点移到链表头部（表示最近访问）cache.splice(cache.begin(), cache, it->second);return it->second->second;}void put(int key, int value) {auto it = record.find(key);if (it != record.end()) {// 更新值并移到链表头部it->second->second = value;cache.splice(cache.begin(), cache, it->second);} else {// 插入新节点到头部cache.emplace_front(key, value);record[key] = cache.begin();// 如果超限，删除尾部节点（最久未访问）if (record.size() > capacity) {record.erase(cache.back().first);cache.pop_back();}}}
};

官方题解是完全自己实现的双链表，这里用list更为简洁

 cache.splice(cache.begin(), cache, it->second);

splice用于移动节点，将it迭代器移动到链表头部，且时间复杂度为O(1)