Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(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.
Follow up: Could you do both operations in O(1) time complexity?
Example:
LRUCache cache = new LRUCache( 2 /* capacity */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // returns 1 cache.put(3, 3); // evicts key 2 cache.get(2); // returns -1 (not found) cache.put(4, 4); // evicts key 1 cache.get(1); // returns -1 (not found) cache.get(3); // returns 3 cache.get(4); // returns 4用改的queue和map实现的。queue用来存储历史，map做cache memory。 queue不能直接用是因为需要把某个节点删除再放到末尾。 put的时间复杂度是O(1)。get在维护queue需要遍历查找key对应的节点，不能达到O(1)，最差是O(n)。
/** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */ #include <map> using namespace std; struct list_node{ int key; struct list_node* next; struct list_node* pre; }; class LRUCache { private: map<int, int> cache_mem; struct list_node *list_head; struct list_node *list_tail; int capacity; int queue_size; public: LRUCache(int capacity) { this->capacity = capacity; queue_size = 0; list_head = list_tail = NULL; } int get(int key) { map<int,int>::iterator it = cache_mem.find(key); if(it == cache_mem.end()) return -1; struct list_node *tmp; for(tmp = list_head;;tmp = tmp->next){ if(tmp->key == key){ if(tmp == list_tail) break; if(tmp == list_head){ list_head = tmp->next; list_head->pre = NULL; } else{ tmp->pre->next = tmp->next; tmp->next->pre = tmp->pre; } list_tail->next = tmp; tmp->pre = list_tail; list_tail = tmp; break; } } return it->second; } void put(int key, int value) { if(get(key) != -1){ map<int,int>::iterator it = cache_mem.find(key); it->second = value; return; } cache_mem.insert(make_pair(key,value)); if(capacity == queue_size){ struct list_node *head = list_head; int k = head->key; cache_mem.erase(k); list_head = head->next; if(list_head != NULL) list_head->pre = NULL; delete head; queue_size--; } struct list_node *tmp = new struct list_node(); tmp->key = key; tmp->next = NULL; tmp->pre = NULL; if(list_head == NULL){ list_head = tmp; list_tail = tmp; } else{ list_tail->next = tmp; tmp->pre = list_tail; list_tail = tmp; } queue_size++; } };
