首页 > 代码库 > LRU Cache
LRU Cache
这个题敲了好久,比较纠结就是用链表加map实现,第一次是用单链表加一个指针标记,提交了几次总是出现runtime error。应该是内存访问出现了问题,原因在指针上,所以我就采用了双链表,修改了几个边界问题终于过了。需要考虑的边界有,catche容量为0,1的情况时head和tail的处理。链表存储的是所有catche中数据的键值,用来确定最近最少访问的顺序,map则存储键和值的对应关系。
其实题目的算法不难,简单说下思路:
(1)当增加一个键时,查看其是否存在,若存在,在map中则更新其值,并将链表中对应该键的节点移到链表尾,若不存在,则插入到链表尾。
(2)如果空间超过catche大小,则删除链表头节点,并删除map中对应的值。
(3)当访问一个键时,如果没有则直接返回-1,否则,将链表中对应的节点移到链表尾。
struct Node{ int key; Node* next; Node* pre;};class LRUCache{private: Node *head,*tail; int CatcheSize=0,capacity=0; map<int,int> m1;public: LRUCache(int capacity) { this->capacity = capacity; head = tail = 0; CatcheSize = 0; } int get(int key) { map<int,int>::iterator it; it = m1.find(key); if(it == m1.end())//如果没有找到,则返回-1 return -1; //找到了,将其移入末尾 Node* tmp = head; for (int i=0;i<CatcheSize;i++) { if(key == tmp->key ) { if(head != tail) { if(tmp == head) { head = head->next; head ->pre =0; tail ->next = tmp; tmp ->pre = tail; tail = tmp; tail ->next = 0; } else if(tmp != tail) { tmp ->pre ->next = tmp -> next; tmp ->next ->pre = tmp ->pre; tail -> next = tmp; tmp -> pre = tail; tail = tmp; tail -> next = 0; } } break; } tmp = tmp->next; } return m1[key]; } void set(int key, int value) { int i=0; //遍历链表,查看这个键是否存在,若存在,则更新其值; //否则,插入改组数据。最后将该键数据移到链表尾部。 Node* tmp = head; for ( i=0;i<CatcheSize;i++) { if(key == tmp->key ) { m1[key] = value; if(head != tail) { if(tmp == head) { head = head->next; head ->pre =0; tail ->next = tmp; tmp ->pre = tail; tail = tmp; tail ->next = 0; } else if(tmp != tail) { tmp ->pre ->next = tmp -> next; tmp ->next ->pre = tmp ->pre; tail -> next = tmp; tmp -> pre = tail; tail = tmp; tail -> next = 0; } } break; } tmp = tmp->next; } //如果链表中不存在该键则新建节点,并链入表尾。 if(i == CatcheSize || CatcheSize == 0) { m1[key] = value; Node* tmp1 = new Node; tmp1 ->key = key; CatcheSize++; if(head != 0) { tail -> next = tmp1; tmp1 -> pre = tail; tail = tmp1 ; tail ->next =0; } else { head = tmp1; tail = tmp1; tail ->next = 0; head ->next = 0; tail ->pre = 0; } } //如果空间已满,则删除头结点 if(CatcheSize > capacity) { Node* fre; fre = head; m1.erase(fre -> key); if(head != tail) head = head ->next; else { head = 0; tail = 0; } delete [] fre; CatcheSize--; } }};
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。