哪个网站开发软件,备案网站域名查询,北京大兴网站建设,wordpress 主页不显示图片2023-09-24每日一题
一、题目编号
146. LRU 缓存二、题目链接
点击跳转到题目位置
三、题目描述
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类#xff1a;
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存i…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_mapint, 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) 双端链表。
