leetcode 面试150之 156.LUR 缓存
请你设计并实现一个满足 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_map<int,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_map<int,listnode*> dp; //精华//初始化 LRUCache(int capacity) {max_=capacity;head=new listnode(0,0);tail=new listnode(0,0);head->next=tail;tail->pre=head;}//双向链表头插法 将处理的node节点 使用优先级提高void addnode(listnode* node){node->next=head->next;head->next->pre=node;head->next=node;node->pre=head;}//断开node节点 并未delete void remove_node(listnode* node){node->pre->next=node->next;node->next->pre=node->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]->val=value; //已经存在 更新val后，取走节点后插入头 提高优先级remove_node(dp[key]);addnode(dp[key]);}//key不存在else{if(max_==dp.size()) //空间已满 删除优先级低节点 也就是 tail->pre{listnode* temp=tail->pre;remove_node(temp);dp.erase(temp->key);delete temp; //释放内存}//无论空间是否够 都需要插入这个key节点listnode* node=new 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);*/