力扣 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)