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
实现LRU
用map+双向链表
C++：
1 class LRUCache { 2 private: 3 struct Node{ 4 int key ; 5 int value ; 6 Node* left ; 7 Node* right ; 8 Node(int k , int v): key(k) , value(v) , left(NULL) , right(NULL) {} 9 }; 10 11 int capacity ; 12 unordered_map<int,Node*> hash ; 13 Node* head ; 14 Node* tail ; 15 16 void deleteNode(Node * node){ 17 node->left->right = node->right ; 18 node->right->left = node->left ; 19 } 20 21 void insertToTail(Node * node){ 22 Node* last = tail->left ; 23 node->right = tail ; 24 node->left = last ; 25 tail->left = node ; 26 last->right = node ; 27 } 28 29 public: 30 LRUCache(int capacity) { 31 this->capacity = capacity ; 32 this->head = new Node(0,0) ; 33 this->tail = new Node(0,0) ; 34 head->right = this->tail ; 35 tail->left = this->head ; 36 } 37 38 int get(int key) { 39 if (hash.count(key) == 0){ 40 return -1 ; 41 }else{ 42 deleteNode(hash[key]) ; 43 insertToTail(hash[key]) ; 44 return hash[key]->value ; 45 } 46 } 47 48 void put(int key, int value) { 49 if (hash.count(key) != 0){ 50 deleteNode(hash[key]) ; 51 insertToTail(hash[key]) ; 52 hash[key]->value = value ; 53 }else{ 54 if (hash.size() < this->capacity){ 55 Node* node = new Node(key,value) ; 56 insertToTail(node) ; 57 hash[key] = node ; 58 }else{ 59 Node* node = head->right ; 60 deleteNode(node) ; 61 insertToTail(node) ; 62 hash.erase(node->key) ; 63 hash[key] = node ; 64 node->key = key ; 65 node->value = value ; 66 } 67 } 68 } 69 }; 70 71 /** 72 * Your LRUCache object will be instantiated and called as such: 73 * LRUCache obj = new LRUCache(capacity); 74 * int param_1 = obj.get(key); 75 * obj.put(key,value); 76 */
java:
1 class LRUCache { 2 3 class ListNode{ 4 int key ; 5 int value ; 6 ListNode pre ; 7 ListNode next ; 8 } 9 10 11 12 private void deleteNode(ListNode node){ 13 node.pre.next = node.next ; 14 node.next.pre = node.pre ; 15 } 16 17 private void insertNode(ListNode node){ 18 ListNode p = head.next ; 19 node.pre = head ; 20 node.next = p ; 21 head.next = node ; 22 p.pre = node ; 23 } 24 25 private Map<Integer,ListNode> map = new HashMap<Integer,ListNode>() ; 26 private ListNode head ; 27 private ListNode tail ; 28 private int count = 0 ; 29 private int capacity ; 30 31 public LRUCache(int capacity) { 32 head = new ListNode() ; 33 tail = new ListNode() ; 34 head.pre = null ; 35 head.next = tail ; 36 tail.pre = head ; 37 tail.next = null ; 38 this.capacity = capacity ; 39 } 40 41 public int get(int key) { 42 ListNode node = map.get(key) ; 43 if (node == null){ 44 return -1 ; 45 }else{ 46 deleteNode(node) ; 47 insertNode(node) ; 48 return node.value ; 49 } 50 } 51 52 public void put(int key, int value) { 53 ListNode node = map.get(key) ; 54 if (node == null){ 55 ListNode newNode = new ListNode(); 56 newNode.key = key; 57 newNode.value = value; 58 map.put(key,newNode) ; 59 insertNode(newNode) ; 60 count++ ; 61 if (count > capacity){ 62 ListNode last = tail.pre ; 63 deleteNode(last) ; 64 count-- ; 65 map.remove(last.key) ; 66 } 67 }else{ 68 node.value = value ; 69 deleteNode(node) ; 70 insertNode(node) ; 71 } 72 } 73 } 74 75 /** 76 * Your LRUCache object will be instantiated and called as such: 77 * LRUCache obj = new LRUCache(capacity); 78 * int param_1 = obj.get(key); 79 * obj.put(key,value); 80 */