Cracking LeetCode: 146. LRU Cache
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
Thought:
For each key, I create a hash list to store a sublist consisting of val, more recently used cache(pre), less recently used cache(next)
h[key]=[val,pre,next]
Use this as a double linked list.
When doing the putting or getting operation, I modify the specific key’s info with its neighbours’ info.
|
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 74 |
#self.h[key] = [val, prev, next] class LRUCache(object): def __init__(self, capacity): """ :type capacity: int """ self.h = {} self.capacity = capacity self.recent = None self.last = None def get(self, key): """ :type key: int :rtype: int """ if key in self.h: if self.recent != key: prev = self.h[key][1] next = self.h[key][2] #link the specified node's previous node to its next node if next: self.h[next][1] = self.h[key][1] if prev: self.h[prev][2] = self.h[key][2] if self.last == key: self.last = prev #change the most recent node's prev info self.h[self.recent][1] = key #set this key as the recent key and link the previous recent key to its next self.h[key][1] = key self.h[key][2] = self.recent self.recent = key return self.h[key][0] else: return -1 def put(self, key, value): """ :type key: int :type value: int :rtype: void """ if self.get(key) != -1: self.h[key][0] = value else: self.h[key] = [value, None, self.recent] if self.recent: self.h[self.recent][1] = key if not self.last: self.last = key self.recent = key if len(self.h) > self.capacity: last = self.h[self.last][1] self.h.pop(self.last, None) self._setaslast(last) def _setaslast(self, key): self.last = key self.h[key][2] = None # Your LRUCache object will be instantiated and called as such: # obj = LRUCache(capacity) # param_1 = obj.get(key) # obj.put(key,value) |
Comments
Comments are closed.