2023-09-24 LeetCode每日一题(LRU 缓存)

2023-09-24每日一题

一、题目编号

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) 的平均时间复杂度运行。

四、解题代码

struct DLinkedNode {int key, value;DLinkedNode* prev;DLinkedNode* next;DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};class LRUCache {
private:unordered_map<int, DLinkedNode*> cache;DLinkedNode* head;DLinkedNode* tail;int size;int capacity;public:LRUCache(int _capacity): capacity(_capacity), size(0) {// 使用伪头部和伪尾部节点head = new DLinkedNode();tail = new DLinkedNode();head->next = tail;tail->prev = head;}int get(int key) {if (!cache.count(key)) {return -1;}// 如果 key 存在，先通过哈希表定位，再移到头部DLinkedNode* node = cache[key];moveToHead(node);return node->value;}void put(int key, int value) {if (!cache.count(key)) {// 如果 key 不存在，创建一个新的节点DLinkedNode* node = new DLinkedNode(key, value);// 添加进哈希表cache[key] = node;// 添加至双向链表的头部addToHead(node);++size;if (size > capacity) {// 如果超出容量，删除双向链表的尾部节点DLinkedNode* removed = removeTail();// 删除哈希表中对应的项cache.erase(removed->key);// 防止内存泄漏delete removed;--size;}}else {// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部DLinkedNode* node = cache[key];node->value = value;moveToHead(node);}}void addToHead(DLinkedNode* node) {node->prev = head;node->next = head->next;head->next->prev = node;head->next = node;}void removeNode(DLinkedNode* node) {node->prev->next = node->next;node->next->prev = node->prev;}void moveToHead(DLinkedNode* node) {removeNode(node);addToHead(node);}DLinkedNode* removeTail() {DLinkedNode* node = tail->prev;removeNode(node);return node;}
};

五、解题思路

(1) 双端链表。