变量简洁正确完整思路
哈希表key2node，双向队列cache存放pair，
对于put，如果key在key2ndoe中提前删除，如果cache等于最大容量maxCapacity提前删除key2node中的cache最后一个和删除cache最后一个，更新cache和key2node，{key,node}放入cache前面并更新key2node[key]
对于get，如果key2node找不到keyreturn-1，将{key,val}从key2node取出，更新cache，cache删除key2node[key]指向的节点并将该节点放到cache前面，更新key2node[key]，key2node[key]指向cache前面，返回val
精确定义
key2node哈希表，key映射一个迭代器，指向cache中{key,value}
cache双向链表，保存{key，value}
class LRUCache { public: LRUCache(int capacity) :maxCapacity(capacity){} int get(int key) { if(!key2node.count(key))return -1; cache.splice(cache.begin(),cache,key2node[key]); return key2node[key]->second; } void put(int key, int value) { if(key2node.count(key))cache.erase(key2node[key]); if(cache.size()==maxCapacity){ key2node.erase(cache.back().first); cache.pop_back(); } cache.push_front({key,value}); key2node[key]=cache.begin(); } private: list<pair<int,int>>cache; unordered_map<int,list<pair<int,int>>::iterator>key2node; int maxCapacity; };
踩过的坑
list<pair<int,int>>cache;list小写
cache.erase(key2node[key]);哈希表才能用val来删除，这个list用迭代器删除
if(key2node.count(key))cache.erase(key2node[key]);哈希表查找，list需要迭代器才能删除
key2node.erase(cache.back().first);删除key2node中cache最后一个
cache.splice(cache.begin(),cache,key2node[key]);将cache的key2node[key]
指向的节点接到cache的cache.begin()迭代器指向的节点前面
详细思路
在原来的基础上修改，实现myList和Node，实现myList一些
struct Node{ Node(int key,int value):key(key),value(value){} int key; int value; Node *prev; Node *next; }; class myList{ public: myList(){ head=new Node(-1,-1); tail=new Node(-1,-1); head->next=tail; tail->prev=head; mSize=0; } void splice(Node *it1, myList l2, Node*it2){ it2->prev->next=it2->next; it2->next->prev=it2->prev; it2->prev=it1->prev; it2->next=it1; it1->prev->next=it2; it1->next->prev=it2; mSize++; } Node *begin() { return head->next; } void erase(Node *it) { it->prev = it->next; mSize--; delete it; } int size() { return mSize; } Node* back() { return tail->prev; } void pop_back(){ tail = tail->prev; mSize--; delete tail->next; } void push_front(Node*node){ node->prev = head; node->next = head->next; head->next = node; node->next->prev = node; mSize++; } private: Node* head,*tail; int mSize; }; class LRUCache { public: LRUCache(int capacity) :maxCapacity(capacity){} int get(int key) { if(!key2node.count(key))return -1; cache.splice(cache.begin(),cache,key2node[key]); return key2node[key]->value; } void put(int key, int value) { if(key2node.count(key))cache.erase(key2node[key]); if(cache.size()==maxCapacity){ key2node.erase(cache.back()->key); cache.pop_back(); } Node *node =new Node(key, value); cache.push_front(node); key2node[key]=cache.begin(); } private: myList cache; unordered_map<int,Node*>key2node; int maxCapacity; };