题目
腾讯后台开发手撕常考
请你设计并实现一个满足 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)
的平均时间复杂度运行。
示例
示例:
输入 ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4] 解释 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4
分析
为了实现一个满足 LRU(最近最少使用)缓存约束的数据结构,并且保证 get
和 put
操作的平均时间复杂度为 O(1),可以结合使用哈希表和双向链表。哈希表用于快速查找键值对,双向链表用于维护键值对的访问顺序。
哈希表+双向链表
get(int key)
函数:
首先在哈希表中查找 key
,如果不存在,返回 -1;如果存在,将该元素移动到链表头部,表示最近访问,并更新哈希表中该元素的迭代器。
返回该元素的值。
put(int key, int value)
函数:
如果 key
已经存在,删除链表中对应的元素;如果缓存已满,删除链表尾部的元素,并从哈希表中移除对应的键。
插入新的键值对到链表头部,并更新哈希表。
时间复杂度:O(1)
空间复杂度:O(capacity)
class LRUCache {
private:
int capacity;
std::list<std::pair<int, int>> cacheList;
std::unordered_map<int, std::list<std::pair<int, int>>::iterator> cacheMap;
public:
LRUCache(int capacity) : capacity(capacity) {}
int get(int key) {
auto it = cacheMap.find(key);
if (it == cacheMap.end()) {
return -1;
}
// 将该元素移动到链表头部
std::pair<int, int> kv = *(it->second);
cacheList.erase(it->second);
cacheList.push_front(kv);
cacheMap[key] = cacheList.begin();
return kv.second;
}
void put(int key, int value) {
auto it = cacheMap.find(key);
if (it != cacheMap.end()) {
// 如果 key 已经存在,更新其值并移动到链表头部
cacheList.erase(it->second);
} else if (cacheList.size() == capacity) {
// 如果缓存已满,删除链表尾部元素
int lastKey = cacheList.back().first;
cacheMap.erase(lastKey);
cacheList.pop_back();
}
// 插入新元素到链表头部
cacheList.push_front({key, value});
cacheMap[key] = cacheList.begin();
}
};
知识充电
std::pair 模板类
定义
template< class T1, class T2 >
struct pair;
创建和初始化
#include <iostream>
#include <utility>
#include <string>
int main() {
// 默认构造函数,元素进行默认初始化
std::pair<int, double> p1;
// 直接使用值进行初始化
std::pair<int, std::string> p2(1, "example");
// 使用 std::make_pair 函数创建,自动推导类型
auto p3 = std::make_pair(2, 3.14);
std::cout << "p2: (" << p2.first << ", " << p2.second << ")" << std::endl;
std::cout << "p3: (" << p3.first << ", " << p3.second << ")" << std::endl;
return 0;
}
访问元素
std::pair
提供了两个公有成员变量first
和second
,借助它们可以分别访问pair
中的第一个和第二个元素:
#include <iostream>
#include <utility>
int main() {
std::pair<int, char> p(10, 'A');
std::cout << "First element: " << p.first << std::endl;
std::cout << "Second element: " << p.second << std::endl;
return 0;
}
比较操作
std::pair
重载了多个比较运算符,像==
、!=
、<
、<=
、>
、>=
等,能直接对两个pair
对象进行比较。比较时先比较first
成员,若相等再比较second
成员:
#include <iostream>
#include <utility>
int main() {
std::pair<int, int> p1(1, 2);
std::pair<int, int> p2(1, 2);
std::pair<int, int> p3(2, 3);
std::cout << std::boolalpha;
std::cout << "p1 == p2: " << (p1 == p2) << std::endl;
std::cout << "p1 < p3: " << (p1 < p3) << std::endl;
return 0;
}
交换操作
#include <iostream>
#include <utility>
int main() {
std::pair<int, char> p1(1, 'A');
std::pair<int, char> p2(2, 'B');
p1.swap(p2);
std::cout << "p1: (" << p1.first << ", " << p1.second << ")" << std::endl;
std::cout << "p2: (" << p2.first << ", " << p2.second << ")" << std::endl;
return 0;
}
std::pair
是一个简单却实用的模板类,它可以方便地把两个不同类型的值组合在一起,并且提供了访问元素、比较和交换等操作,在许多算法和数据处理场景中都有广泛应用。