LeetCode [146] LRU Cache

146. LRU Cache

Medium

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

Follow up:
Could you do get and put in O(1) time complexity?

 

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

 

Constraints:

• 1 <= capacity <= 3000
• 0 <= key <= 3000
• 0 <= value <= 104
• At most 3 * 104 calls will be made to get and put.

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

class LRUCache { struct ND { int k, v; ND* prev; ND* next; ND(int _k, int _v):k(_k), v(_v), prev(NULL), next(NULL){} ND():prev(NULL), next(NULL){} }; ND* H; ND* T; int sz, cap; unordered_map<int, ND*> mp;//key, ND void add(ND* nd){ T->prev->next = nd; nd->prev = T->prev; nd->next = T; T->prev = nd; } int rm(ND* nd) { int k = nd->k; nd->prev->next = nd->next; nd->next->prev = nd->prev; return k; } void mv2end(ND* nd) { rm(nd); add(nd); } public: LRUCache(int capacity) { H = new ND(); T = new ND(); H->next = T; T->prev = H; sz = 0; cap = capacity; } int get(int key) { if(mp.find(key)==mp.end()){ return -1; }else{ ND* nd = mp[key]; mv2end(nd); return nd->v; } } void put(int key, int value) { if(mp.find(key)!=mp.end()){ ND* nd = mp[key]; nd->v = value; mv2end(nd); }else{ ND* nd = new ND(key, value); add(nd); mp[key] = nd; if(sz<cap){ sz++; }else{ ND* head = H->next; rm(head); mp.erase(head->k); } } } };

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

class LRUCache { Node head = new Node(0, 0), tail = new Node(0, 0); Map<Integer, Node> map = new HashMap(); int capacity; public LRUCache(int _capacity) { capacity = _capacity; head.next = tail; tail.prev = head; } public int get(int key) { if(map.containsKey(key)) { Node node = map.get(key); remove(node); insert(node); return node.value; } else { return -1; } } public void put(int key, int value) { if(map.containsKey(key)) { remove(map.get(key)); } if(map.size() == capacity) { remove(tail.prev); } insert(new Node(key, value)); } private void remove(Node node) { map.remove(node.key); node.prev.next = node.next; node.next.prev = node.prev; } private void insert(Node node){ map.put(node.key, node); Node headNext = head.next; head.next = node; node.prev = head; headNext.prev = node; node.next = headNext; } class Node{ Node prev, next; int key, value; Node(int _key, int _value) { key = _key; value = _value; } } } /** * 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); */