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);*/