电商网站如何设计内容,响应式网站制设计,定制开发小程序报价,服务器网站建设实训报告请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类#xff1a;
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中#xff0c;则返回关键字的值#xff0c;否则返回 -…
请你设计并实现一个满足 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) 的平均时间复杂度运行。
题目重点O(1)实现查找和删除
O(1)查找我们可以通过unordered_map底层哈希表来实现 这里我们如果缓存满了还得删除最久未使用关键字 所以我们得使用一个O(1)维护的“使用队列”数组我们无法实现O(1)删除而双向链表能实现O(1)删除但是无法实现O(1)查询
所以我们这里用到了unordered_mapint,listnode*映射为listnode*通过map去实现O(1)查询 而listnode*双向链表实现O(1)插入和删除
起初我并未想到用双向链表而是用deque去维护“使用队列”后者在维护队列无法做到O(1),包超时的
上代码
class LRUCache {
public:struct listnode{int key;int val;listnode* pre;listnode* next;listnode(int k,int v):key(k),val(v),pre(nullptr),next(nullptr){}};int max_; //最大空间listnode* head; //头哨兵节点listnode* tail; //尾哨兵节点unordered_mapint,listnode* dp; //精华//初始化 LRUCache(int capacity) {max_capacity;headnew listnode(0,0);tailnew listnode(0,0);head-nexttail;tail-prehead;}//双向链表头插法 将处理的node节点 使用优先级提高void addnode(listnode* node){node-nexthead-next;head-next-prenode;head-nextnode;node-prehead;}//断开node节点 并未delete void remove_node(listnode* node){node-pre-nextnode-next;node-next-prenode-pre;}//查询数据int get(int key) {if(dp.count(key)) //查询成功 提高该节点的“使用队列”优先级{remove_node(dp[key]);addnode(dp[key]);return dp[key]-val;}else return -1;}//插入数据void put(int key, int value) {if(dp.count(key)){dp[key]-valvalue; //已经存在 更新val后取走节点后插入头 提高优先级remove_node(dp[key]);addnode(dp[key]);}//key不存在else{if(max_dp.size()) //空间已满 删除优先级低节点 也就是 tail-pre{listnode* temptail-pre;remove_node(temp);dp.erase(temp-key);delete temp; //释放内存}//无论空间是否够 都需要插入这个key节点listnode* nodenew listnode(key,value); addnode(node);dp.insert({key,node});}}
};/*** Your LRUCache object will be instantiated and called as such:* LRUCache* obj new LRUCache(capacity);* int param_1 obj-get(key);* obj-put(key,value);*/
