[LeetCode] 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.

思路：

LRU cache数据结构的核心就是当存储空间满了，而有新的item要插入时，要先丢弃最早更新的item。这里的数据结构需要符合以下条件：

1. 要能快速找到最早更新的item。这里需要将item以更新时间顺序排序。
可选的有：queue，heap，linked list

2. 要能快速访问指定item，并且访问以后要更新它的时间顺序。
对于更新时间顺序这个操作，queue和heap要做到就很困难了。所以这点最佳的是linked list。但linked list中查找指定item需要遍历，这里可以用一个hash table来记录key与节点之间的对应。并且由于要随时更新节点位置，doubly linked list更为适用。

根据以上两点，有了以下解法。注意由于代码较长，面试时尽可能将一些基本操作写成函数。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91

class LRUCache{ struct Node { int val; int key; Node *next; Node *prev; Node(int k, int v):key(k),val(v) {} }; int maxSize; Node* head; Node* tail; unordered_map<int,Node*> keyToNode; void insertToEnd(int key, int value) { if(isFull() || keyToNode.count(key)!=0) return; Node *nd = new Node(key, value); keyToNode[key] = nd; if(!head) { head = tail = nd; } else { tail->next = nd; nd->prev = tail; tail = tail->next; } } void removeHead() { if(!head) return; keyToNode.erase(head->key); Node *temp = head; if(head==tail) // only one node remain head = tail = NULL; else { head = head->next; head->prev = NULL; } delete temp; } void moveToEnd(int key) { // key not exist, or already at the end if(keyToNode.count(key)==0 || keyToNode[key]==tail) return; Node *nd = keyToNode[key]; if(nd==head) { head = head->next; head->prev = NULL; } else { // not head, not tail nd->prev->next = nd->next; nd->next->prev = nd->prev; } tail->next = nd; nd->prev = tail; nd->next = NULL; tail = tail->next; } public: LRUCache(int capacity) { maxSize = capacity; head = NULL; tail = NULL; keyToNode.clear(); } int get(int key) { if(keyToNode.count(key)==0) return -1; moveToEnd(key); return keyToNode[key]->val; } void set(int key, int value) { // key already exists if(get(key)!=-1) { keyToNode[key]->val = value; return; } // key not exist, insert new node if(isFull()) removeHead(); insertToEnd(key, value); } bool isFull() { return keyToNode.size()>=maxSize; } };