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.
这个题目考的非常综合。
类似问题考虑要点：
1. get，算是cache hit，首先要查找到这个node，然后再把这个node放到第一位
2. setval, 这个算是更新，如果找到，那么把他移到头上，如果找不到那就新建一个放到第一位。
因为涉及到元素的顺序，元素的更新，那么vector based的方案，统统不行。
最直接的实现是使用 double link list，然后查找就是线性查找，插入，删除O（1）但是当链表比较大时，查找就很慢。
需要查找快，那么就是hash或者map 这里最最合适的就是hash。
所以要搞出一个比较诡异的结构，
把双向链表放到一个以Key为哈希key的hash表中。
那么在查找的时候可以利用hash的O（1），快速的判断key是否在链表中。
当找到key之后，找到对应的链表结点，然后通过O(1)的复杂度，来更新链表。
另外一个trick是链表的操作中，使dumb node ，非常有助于简化问题。
因为是双向队列，所以使用两个dumb node。
class LRUCache{ public: struct LinkList { int val; int key; LinkList* next; LinkList* prev; LinkList(int k, int x) : key(k), val(x), next(NULL), prev(NULL){} }; //link list operation to simplify operation introuduce 2 dummy node, head and tail LinkList *tail = NULL; LinkList *head = NULL; int gcapcity = 0; int size = 0; // due to performance hit, so put the key in the map or hastable, will // directly improve the performance of searching, actually,searching directly based on the map/hastable // unordered_map<int, LinkList*> nodeMap; LRUCache(int capacity) { gcapcity = capacity; tail = new LinkList(-1, -1); head = new LinkList(-1, -1); head->next = tail; tail->prev = head; size = 0; } void PutSingleNodetoHead(LinkList* node) { if (node == NULL) return; node->next = head->next; node->prev = head; head->next->prev = node; head->next = node; } int get(int key) { int val = -1; unordered_map<int, LinkList*>::iterator it = nodeMap.find(key); if (it != nodeMap.end()) //found { LinkList* node = it->second; val = node->val; node->prev->next = node->next; node->next->prev = node->prev; PutSingleNodetoHead(node); } return val; } void set(int key, int value) { unordered_map<int, LinkList*>::iterator it = nodeMap.find(key); if (it == nodeMap.end()) { //not exist need insert one LinkList *node = new LinkList(key, value); PutSingleNodetoHead(node); nodeMap[key] = node; size++; if(size>gcapcity){ node = tail->prev; tail->prev = node->prev; node->prev->next = tail; it = nodeMap.find(node->key); nodeMap.erase(it); delete node; } } else { LinkList* ptnode = it->second; ptnode->val = value; ptnode->prev->next = ptnode->next; ptnode->next->prev = ptnode->prev; PutSingleNodetoHead(ptnode); } } };