【LeetCode】LRU Cache
LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get
and set
.
get(key)
- Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.set(key, value)
- Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
这题关键在于,怎样判断每个value是否算“最近使用”?
一个简单的想法是对每个键值对保留一个使用时间,当cache满时,删除最小时间对应的键值对。
问题在于寻找最小时间需要遍历,O(n)超时。
我们考虑使用空间换时间,建立一个双向链表,最近使用的调整到头部,需要删除则删除尾部。
代码实现如下:
struct BiListNode { int key; BiListNode* prev; BiListNode* next; BiListNode(int k): key(k), prev(NULL), next(NULL){} }; class LRUCache { public: int capacity; map<int, int> LRU; BiListNode* head; //head point to the recently used (key,value) BiListNode* tail; //tail point to the recently unused (key,value) map<int, BiListNode*> m; LRUCache(int capacity) { this->capacity = capacity; head = NULL; tail = NULL; } int get(int key) { map<int, int>::iterator it = LRU.find(key); if(it != LRU.end()) {//find //update the sequence //the newly used node, move it to head BiListNode* target = (m.find(key))->second; if(target != head) { //target != head means target has prev target->prev->next = target->next; if(target->next != NULL) target->next->prev = target->prev; else {//target is the tail tail = target->prev; } target->next = head; head->prev = target; target->prev = NULL; //new head head = target; } return it->second; } else return -1; } void set(int key, int value) { map<int, int>::iterator it = LRU.find(key); if(it != LRU.end()) {//find, update //update the value it->second = value; //the newly used node, move it to head BiListNode* target = (m.find(key))->second; if(target != head) { //target != head means target has prev target->prev->next = target->next; if(target->next != NULL) target->next->prev = target->prev; else {//target is the tail tail = target->prev; } target->next = head; head->prev = target; target->prev = NULL; //new head head = target; } } else {//add, maybe delete first if(LRU.size() == capacity) {//full, delete first //delete from list if(tail->prev != NULL) tail->prev->next = NULL; //delete from map map<int, BiListNode*>::iterator it = m.find(tail->key); m.erase(it); //delete from LRU map<int, int>::iterator it2 = LRU.find(tail->key); LRU.erase(it2); tail = tail->prev; } //add to list if(head == NULL) { head = new BiListNode(key); tail = head; } else { BiListNode* temp = new BiListNode(key); temp->next = head; head->prev = temp; head = temp; } //add to map m.insert(map<int, BiListNode*>::value_type(key, head)); //add LRU.insert(map<int, int>::value_type(key, value)); } } };
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。