【力扣刷题练习】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) 的平均时间复杂度运行。

题目解答：

class LRUCache {  
private:  
    // 缓存容量  
    int cap;  
    // 缓存项列表，每个缓存项是一个键值对  
    list<pair<int, int>> cache;  
    // 哈希表，用于存储键到缓存项迭代器的映射  
    unordered_map<int, list<pair<int, int>>::iterator> map;  
  
public:  
    // 构造函数，接受一个整数参数capacity，表示缓存容量  
    LRUCache(int capacity) {   
        cap = capacity; // 初始化缓存容量  
    }  
  
    // 获取指定键的值，如果键不存在则返回-1  
    int get(int key) {  
        auto it = map.find(key); // 在哈希表中查找键  
        if (it == map.end()) // 如果键不存在于哈希表中  
            return -1; // 返回-1表示键不存在  
        cache.splice(cache.begin(), cache, it->second); // 将对应的缓存项移到列表前端  
        return it->second->second; // 返回键对应的值  
    }  
  
    // 将键值对添加到缓存中，如果键已存在则更新其值，如果缓存已满则删除最少使用的缓存项  
    void put(int key, int value) {  
        auto it = map.find(key); // 在哈希表中查找键  
        if (it != map.end()) { // 如果键已存在于哈希表中  
            cache.splice(cache.begin(), cache, it->second); // 将对应的缓存项移到列表前端，以便更新值  
            it->second->second = value; // 更新键对应的值  
            return; // 结束函数调用  
        }  
        if (cache.size() == cap) { // 如果缓存已满  
            map.erase(cache.back().first); // 从哈希表中删除最少使用的缓存项的键  
            cache.pop_back(); // 从列表中删除最少使用的缓存项  
        }  
        cache.push_front({key, value}); // 在列表前端添加新的缓存项  
        map[key] = cache.begin(); // 在哈希表中添加键到缓存项迭代器的映射  
    }  
};

题目思路：

全文背诵并默写
按照题目给的板子去实现了LRU缓存的基本功能：能够快速获取指定键的值，并在缓存已满时删除最少使用的缓存项。通过使用双向链表和哈希表，该实现能够在常数时间内完成获取、插入和删除操作，从而提供高效的缓存管理。