LRU Cache -- LeetCode
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations:
get
andset
.
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.
题目描述如上,就是设计一个数据结构,实现LRU算法,支持两种操作,get(查询key对应的value),和set(将key,value加入集合中)
首先,我用双向链表实现,代码细节需要注意的地方较多,因为是处理指针。
1 class LRUCache{ 2 public: 3 class Node { 4 public: 5 int key, value; 6 Node *prv, *nxt; 7 Node():key(0), value(0), prv(NULL), nxt(NULL) {} 8 Node(int key, int val):key(key), value(val), prv(NULL), nxt(NULL) {} 9 }; 10 class DoubleLinkedList { 11 public: 12 Node *head, *tail; 13 int size, capacity; 14 DoubleLinkedList():size(0), capacity(0), head(NULL), tail(NULL) {} 15 DoubleLinkedList(int c):size(0), capacity(c), head(NULL), tail(NULL) {} 16 /*~DoubleLinkedList() { 17 while (head != NULL) { 18 Node *tmp = head; 19 head = head->nxt; 20 delete tmp; 21 } 22 }*/ 23 void erase(Node *it) { 24 if (size == 0) return ; 25 if (it->prv != NULL && it->nxt != NULL) { 26 it->prv->nxt = it->nxt; 27 it->nxt->prv = it->prv; 28 } 29 if (it->prv == NULL) { 30 head = it->nxt; 31 if (head != NULL) 32 head->prv = NULL; 33 } 34 if (it->nxt == NULL) { 35 tail = it->prv; 36 if (tail != NULL) 37 tail->nxt = NULL; 38 } 39 size--; 40 } 41 int insert(Node *it) { 42 if (tail != NULL) { 43 tail->nxt = it; 44 it->nxt = NULL; 45 it->prv = tail; 46 tail = it; 47 } else { 48 head = tail = it; 49 } 50 //if (head == NULL) head = it; 51 //if (tail == NULL) tail = it; 52 size++; 53 if (size > capacity && size > 0) { 54 int key = head->key; 55 if (size == 1) { 56 delete head; 57 head = tail = NULL; 58 } else { 59 Node *tmp = head; 60 head = head->nxt; 61 head->prv = NULL; 62 delete tmp; 63 tmp = NULL; 64 } 65 size--; 66 return key; 67 } 68 return -1; 69 } 70 }; 71 LRUCache(int capacity) { 72 //DoubleLinkedList DLL(capacity); 73 DLL.capacity = capacity; 74 } 75 76 int get(int key) { 77 if (HashMap.find(key) == HashMap.end()) { 78 return -1; 79 } else { 80 Node *it = HashMap[key]; 81 DLL.erase(it); 82 DLL.insert(it); 83 return (it->value); 84 } 85 } 86 87 void set(int key, int value) { 88 if (HashMap.find(key) != HashMap.end()) { 89 Node *it = HashMap[key]; 90 it->value = value; 91 DLL.erase(it); 92 DLL.insert(it); 93 } else { 94 Node *tmp = new Node(key, value); 95 HashMap.insert(pair<int, Node*>(key, tmp)); 96 int k = DLL.insert(tmp); 97 if (k != -1) HashMap.erase(k); 98 } 99 } 100 101 private: 102 unordered_map<int, Node*> HashMap; 103 DoubleLinkedList DLL; 104 };
后来,有人说可以用list来简化代码,我原以为面试的时候应该尽量少的使用STL等高级手段,后来巨巨们说并不是这样,于是就用list实现了一遍。
1 class LRUCache{ 2 public: 3 LRUCache(int c) { 4 capacity = c; 5 } 6 7 int get(int key) { 8 int ans = -1; 9 auto it = disc.find(key); 10 if (it != disc.end()) { 11 ans = it->second->second; 12 data.erase(it->second); 13 data.push_front(pair<int, int>(key, ans)); 14 disc[key] = data.begin(); 15 } 16 return ans; 17 } 18 19 void set(int key, int value) { 20 auto it = disc.find(key); 21 if (it != disc.end()) { 22 data.erase(it->second); 23 data.push_front(pair<int, int>(key, value)); 24 disc[key] = data.begin(); 25 } else { 26 data.push_front(pair<int, int>(key, value)); 27 disc[key] = data.begin(); 28 if (data.size() > capacity) { 29 auto it2 = data.end(); it2--; 30 int k = it2->first; 31 disc.erase(k); 32 data.pop_back(); 33 } 34 } 35 } 36 private: 37 unordered_map<int, list<pair<int, int> >::iterator > disc; 38 list<pair<int, int> > data; 39 int capacity; 40 };
代码较之前短了很多,但是时间效率也是慢了一倍。
后来听说到有个东西unique_ptr,智能指针,虽然没有使用过,不过还是看了下介绍,可以省去delete操作,方便而且不容易出错。
另外,在使用list解答 本题的时候发现原来我一直没有真正理解迭代器这个概念。我们熟悉的指针也是一种迭代器,但是不可以说迭代器就是指针。
比如,数组下标也是一种迭代器,但是他就不是地址。
当使用list.erase(it)操作时,他返回的是下一个元素的迭代器,而it对应的元素已经被销毁,所以it不可以继续使用,
可以这样:
it = list.erase(it)
或者:
list.erase(it++)
下面一种方法中,在it被erase之前,已经做了一次后自增,所以此时的it是指向下一个元素的,删除了的是it之前的那个元素。
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。