[LeetCode 热门话题 100] [链表] LRU 缓存
最编程
2024-07-03 19:51:35
...
我昨天面了天美L1的游戏客户端开发,面了我100分钟,问完实习、项目、计算机图形学和C++后给了我两道算法题做,一道是最长公共子序列,一道是LRU缓存,我知道是经典的题目,但是我都没敲过,我之前写过一个KV的数据库系统用过LRU(最近最少使用)缓存,用的是双向链表和哈希表解决的,当时是实现了一个双向链表,用来存储value,哈希表存储key和对应存储value的链表节点的指针,最近被访问的key就把它的节点移到链表头,超过容量就删掉链表尾
原题:146. LRU 缓存 - 力扣(LeetCode)
手动实现一个双向链表,用来存储key和value,哈希表存储key和对应链表节点的指针,链表存储key是为了删除哈希表中的元素
get首先判断key在不在,在的话,通过哈希表找到节点指针,移动到链表开头,返回value
put首先判断key在不在,在的话,通过哈希表找到节点指针,移动到链表开头,更新value,不在的话,创建一个新的节点插到链表头,添加key和指针到哈希表,如果超过容量,根据链表尾部的key删除哈希表中的元素,再删掉该链表节点
实现细节上,为了插入和删除的方便,使用一个头部和一个尾部节点作为界限,不存储数据
class LRUCache {
private:
struct Node {
int key = 0, value = 0;
Node *prev = nullptr, *next = nullptr;
explicit Node(int key = 0, int value = 0) : key(key), value(value) {}
};
unordered_map<int, Node *> cache;
Node *head, *tail;
int size, capacity;
inline void moveToHead(Node *node) { // 将节点插到链表头部的后面
node->prev = head; // 牵头
node->next = head->next; // 交尾
head->next->prev = node; // 后面牵头
head->next = node; // 前面交尾
}
inline void removeNode(Node *node) { // 从链表中摘除节点
node->prev->next = node->next; // 前面交尾
node->next->prev = node->prev; // 后面牵头
}
public:
LRUCache(int capacity) : capacity(capacity), size(0), head(new Node()), tail(new Node()) {
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (cache.find(key) == cache.end()) // 没有
return -1;
Node *node = cache[key];
removeNode(node);
moveToHead(node);
return node->value;
}
void put(int key, int value) {
Node *node = nullptr;
if (cache.find(key) == cache.end()) { // 还没有就创建一个
node = new Node(key, value);
cache[key]=node;
size++;
} else { // 已经有了就更新一下
node = cache[key];
node->value = value;
removeNode(node);
}
moveToHead(node);
if (size > capacity) { // 容量超了
size--;
Node *old = tail->prev;
cache.erase(old->key); // 删除哈希表元素
removeNode(old); // 删除链表节点
delete old;
}
}
};
上一篇: 毕马威:智能之眼:开启汽车感知新时代