首页 > 代码库 > leetcode LRU Cache
leetcode LRU Cache
题目链接。实现一个数据结构用于LRU，最近最少使用，O(1)插入和删除。关于LRU的基本知识可参考here。
先推荐JustDoIT的。
下面是我自己实现的。
class LRUCache{public://146LRU Least Recently Used int LRUsize; struct LRUNode { int key; int value; LRUNode *pre, *next; LRUNode(int x, int y): key(x), value(y), pre(NULL), next(NULL){} }; unordered_map<int, LRUNode *> LRUmap; LRUNode *head = NULL, *tail = NULL; LRUCache(int capacity) { LRUsize = capacity; } int get(int key) { if (LRUmap.count(key)) // if exists { if (head != LRUmap[key] && tail != LRUmap[key]) // 节点在中间 { LRUmap[key] -> pre -> next = LRUmap[key] -> next; LRUmap[key] -> next -> pre = LRUmap[key] -> pre; LRUmap[key] -> next = head; head -> pre = LRUmap[key]; head = LRUmap[key]; head -> pre = NULL; } else if (head != LRUmap[key] && tail == LRUmap[key]) // 节点最后一个则放在头部即可 { tail = LRUmap[key] -> pre; tail -> next = NULL; LRUmap[key] -> pre = NULL; head -> pre = LRUmap[key]; LRUmap[key] -> next = head; head = LRUmap[key]; } return LRUmap[key] -> value; } else return -1; } void set(int key, int value) { if (LRUmap.count(key)) { LRUmap[key] -> value = http://www.mamicode.com/value; // 一定要更新value if (head != LRUmap[key] && tail != LRUmap[key]) // 节点在中间 { LRUmap[key] -> pre -> next = LRUmap[key] -> next; LRUmap[key] -> next -> pre = LRUmap[key] -> pre; LRUmap[key] -> next = head; head -> pre = LRUmap[key]; head = LRUmap[key]; head -> pre = NULL; } else if (head != LRUmap[key] && tail == LRUmap[key]) // 节点最后一个则放在头部即可 { tail = tail -> pre; tail -> next = NULL; LRUmap[key] -> pre = NULL; head -> pre = LRUmap[key]; LRUmap[key] -> next = head; head = LRUmap[key]; } } else { LRUNode *tmp = new LRUNode(key, value); if (head == tail && head == NULL) { head = tmp; tail = tmp; LRUmap[key] = head; } else if (LRUsize == LRUmap.size()) //注意可能容量只为1，满了记得删除 { tmp -> next = head; head -> pre = tmp; head = tmp; LRUmap[key] = tmp; LRUmap.erase(tail -> key); tail = tail -> pre; tail -> next = NULL; } else { tmp -> next = head; head -> pre = tmp; head = tmp; LRUmap[key] = tmp; } } }};
虽然AC了，不过我还在纠结不知道如何delete代码中new出来的内存。如果用java的话就不用delete了。但是看所有的leetcode提交的分布，c++普遍是速度最快的。
貌似给出推荐的JustDOIT的也是没有delete的。
然后我就找啊找。
这一篇写的还不错。里面有原理解释，而且delete在析构中进行。用可用节点的数组存。或者是用原有的已经有的尾部来存新进入的点。这个想法不错。
这题还是考察挺多的。出现频率高，有时间还是要好好消化。
leetcode LRU Cache
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。