网页开发_网络技术基础_跨国网站浏览器_seo教程排名第一

请你设计并实现一个满足 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) 的平均时间复杂度运行。

思路总结：DlinkNode结构体创建双链表，双链表有key和val；
pre和next指针，并且进行初始化。
哈希表cache存着key和双链表节点
初始化head和tail（head和tail并不存储实际数据）
在LRUCache函数中 要clear哈希表，并且把tail加进双链表
在addNode中 如果有 可以直接返回 如果没有就需要弄个cur
把cur放到head的后面最佳
在deltNode中 如果没有 可以直接返回 如果有就erase他
删除的操作就是把他的前后找到 然后前后接上 把他悬挂
在get操作中，如果没有这个 返回-1；
如果有 就要先给他deletNode 再给他addNode
在put操作中，如果有，就先deletNode 再addNode
如果没有，就看看现在的哈希表是不是等于容量
如果等于容量：那就把tail前一个给他deleNode了
如果不等于容量：简单直接addNode。

struct DlinkNode{int key;int val;DlinkNode*pre;DlinkNode*next;DlinkNode():key(-1),val(-1),next(nullptr),pre(nullptr){}DlinkNode(int _key,int _val):key(_key),val(_val),next(nullptr),pre(nullptr){}
};
class LRUCache {
private:
unordered_map<int,DlinkNode*>cache;DlinkNode*head;DlinkNode*tail;int limit;
public:LRUCache(int capacity) {limit=capacity;cache.clear();head=new DlinkNode();tail=new DlinkNode();head->next=tail;tail->pre=head;}int get(int key) {if(!cache.count(key)){return -1;}int val=cache[key]->val;deltNode(key);addNode(key,val);return val;}void put(int key, int value) {if(cache.count(key)){deltNode(key);addNode(key,value);}else{if(cache.size()==limit){deltNode(tail->pre->key);addNode(key,value);}else{addNode(key,value);}}}void addNode(int key,int val){//添加//在头部添加if(cache.count(key)){return;}DlinkNode*cur=new DlinkNode(key,val);cur->next=head->next;head->next->pre=cur;cur->pre=head;head->next=cur;cache[key]=cur;}void deltNode(int key){//删除if(!cache.count(key)){return;}DlinkNode*cur=cache[key];cache.erase(key);DlinkNode*front=cur->pre;DlinkNode*back=cur->next;front->next=back;back->pre=front;cur->pre=nullptr;cur->next=nullptr;}
};