算法知识点————【LRU算法】

思想：淘汰最久没有使用的
应用场景：手机清后台的时候先清最久没有使用的应用
设计一种数据结构：接收一个 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_map<int,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;}}};