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.
-----------------------------------------------------------------
a few improvement
#1 design a doublely-linked list class
#2 have a de-constructor
#3 code re-factory
用了2个dummy, head跟tail
struct LinkedNode { int key; int val; LinkedNode *pre; LinkedNode *next; LinkedNode(int key,int val) { this->key = key; this->val = val; pre = NULL; next = NULL; } }; class LRUCache{ public: LRUCache(int capacity) { this->capacity = capacity; size = 0; head = new LinkedNode(-1,-1); tail = new LinkedNode(-1,-1); head->next = tail; tail->pre = head; } int get(int key) { if (dic.find(key) == dic.end()) { return -1; } LinkedNode *node = removeNode(dic[key]); insertToFront(node); return node->val; } LinkedNode* removeNode(LinkedNode *node) { LinkedNode *preNode = node->pre; LinkedNode *nextNode = node->next; preNode->next = nextNode; nextNode->pre = preNode; return node; } void insertToFront(LinkedNode *node) { LinkedNode *temp = head->next; head->next = node; temp->pre = node; node->next = temp; node->pre = head; } void set(int key, int value) { if (dic.find(key) == dic.end()) { LinkedNode *temp = head->next; LinkedNode *add = new LinkedNode(key,value); head->next = add; add->pre = head; add->next = temp; temp->pre = add; dic[key] = add; size++; }else { LinkedNode *catched = removeNode(dic[key]); insertToFront(dic[key]); dic[key]->val = value; } if (size > capacity) { LinkedNode *catched = removeNode(tail->pre); dic.erase(catched->key); delete catched; size--; } } private: int capacity; int size; LinkedNode *head; LinkedNode *tail; unordered_map<int,LinkedNode*> dic; };
Java, updated on Jun-30th-2018
class LRUCache { private int capacity; private DoublyLinkedNode head; private DoublyLinkedNode tail; private Map<Integer, DoublyLinkedNode> map; public LRUCache(int capacity) { this.capacity = capacity; head = new DoublyLinkedNode(-1, -1); tail = new DoublyLinkedNode(-1, -1); head.next = tail; tail.pre = head; map = new HashMap<>(); } public int get(int key) { if (map.containsKey(key)) { DoublyLinkedNode node = pickupAndReturn(key); insertFront(node); return node.val; } return -1; } public void put(int key, int value) { DoublyLinkedNode node = null; if (!map.containsKey(key)) { node = new DoublyLinkedNode(key, value); map.put(key, node); }else { node = pickupAndReturn(key); node.val = value; } insertFront(node); if (map.size() > capacity) { removeLast(); } } private void removeLast() { int key = tail.pre.key; tail.pre.pre.next = tail; tail.pre = tail.pre.pre; map.remove(key); } private void insertFront(DoublyLinkedNode node) { head.next.pre = node; node.next = head.next; head.next = node; node.pre = head; } private DoublyLinkedNode pickupAndReturn(int key) { DoublyLinkedNode node = map.get(key); node.pre.next = node.next; node.next.pre = node.pre; return node; } } class DoublyLinkedNode{ public DoublyLinkedNode pre; public DoublyLinkedNode next; public int key; public int val; public DoublyLinkedNode(int key, int val) { this.key = key; this.val = val; } } /** * 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); */
No comments:
Post a Comment