博罗网站建设,做自动化设备哪个网站,重庆市区十大景点推荐,wordpress邮件发送超时思想#xff1a;淘汰最久没有使用的 应用场景#xff1a;手机清后台的时候先清最久没有使用的应用 设计一种数据结构#xff1a;接收一个 capacity 参数作为缓存的最大容量#xff0c;然后实现两个 API#xff0c;一个是 put(key, val) 方法存入键值对#xff0c;另一个是…思想淘汰最久没有使用的 应用场景手机清后台的时候先清最久没有使用的应用 设计一种数据结构接收一个 capacity 参数作为缓存的最大容量然后实现两个 API一个是 put(key, val) 方法存入键值对另一个是 get(key) 方法获取 key 对应的 val如果 key 不存在则返回 -1。要求get 和 put 方法必须都是 O(1) 的时间复杂度。 哈希链表哈希的查找配合双向链表的快速插入和删除
class Node{
public:int key,value;Node *prev,*next;Node(int k 0 ,int v 0 ) : key(k),value(v){}
};
class LRUCache{
private:int capacity;Node* dummy;//哨兵unordered_mapint,Node* key_to_value;//删除节点void remove(Node * x){x-prev-next x-next;x-next-prev x-prev;}//添加节点 放到最上面void put_front(Node * x){x-prev dummy;x-next dummy-next;x-prev-next x;x-next-prev x;} //获取节点 抽出放在最上面Node* get_node(int key){auto it key_to_value.find(key);if(it key_to_value.end()) return nullptr;//没找到auto node it-second;//找到的话 map的node节点返回remove(node);put_front(node);return node;}
public:LRUCache(int capacity) : capacity(capacity),dummy(new Node()){dummy-prev dummy;dummy-next dummy;}int get(int key){auto node get_node(key);return node? node-value:-1;}void put(int key,int value){auto node get_node(key);if(node){//有这本书node-value value;return ;}key_to_value[key] node new Node(key,value);//没有这本书put_front(node);//添加if(key_to_value.size() capacity){//添加得判断auto node_back dummy-prev;key_to_value.erase(node_back-key);remove(node_back);delete node_back;}}};
