【力扣刷题练习】146. LRU 缓存

本文主要是介绍【力扣刷题练习】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(); // 在哈希表中添加键到缓存项迭代器的映射  }  
};