Question: https://oj.leetcode.com/problems/lru-cache/
Question Name: LRU Cache
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 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 | class LRUCache: # The following support functions for priority queue is unnecessary, if we can # import and use Python build-in lib heapq. # @param pos, an integer # @return None def _swinm(self, pos): ''' https://d396qusza40orc.cloudfront.net/algs4partI/slides/24PriorityQueues.pdf Support function for priority queue ''' while pos > 0 and self.heap[(pos-1)//2][2] > self.heap[pos][2]: # Update the position dict. self.position[self.heap[(pos-1)//2][0]] = pos self.position[self.heap[pos][0]] = (pos-1)//2 # Swap these two records in heap self.heap[(pos-1)//2], self.heap[pos] = self.heap[pos], self.heap[(pos-1)//2] pos = (pos-1)//2 return # @param pos, an integer # @return None def _sink(self, pos): ''' https://d396qusza40orc.cloudfront.net/algs4partI/slides/24PriorityQueues.pdf Support function for priority queue ''' while 2*pos + 1 < self.count: earlierSon = 2*pos + 1 # Check the time of its right son, if it exists. if earlierSon+1 < self.count and self.heap[earlierSon][2] > self.heap[earlierSon+1][2]: earlierSon += 1 # Has earlier timestamp than son(s). Finish sinking. if self.heap[earlierSon][2] > self.heap[pos][2]: break # Swap the records in heap and position dict. self.position[self.heap[pos][0]] = earlierSon self.position[self.heap[earlierSon][0]] = pos self.heap[pos], self.heap[earlierSon] = self.heap[earlierSon], self.heap[pos] pos = earlierSon return # @return an array for the least recent used record, in form of [key, value, time] def _popLRU(self): ''' https://d396qusza40orc.cloudfront.net/algs4partI/slides/24PriorityQueues.pdf Support function for priority queue ''' # Nothing to pop. if self.count == 0: return None # Keep the to-pop record, and delete it from position dict. result = self.heap[0] del self.position[result[0]] # Delete the record in the heap. if self.count > 1: self.heap[0] = self.heap[self.count-1] self.count -= 1 self.position[self.heap[0][0]] = 0 self._sink(0) else: self.count -= 1 return result # @param key, an integer # @param value, an integer # @param time, an integer # @return None def _addNew(self, key, value, time): ''' https://d396qusza40orc.cloudfront.net/algs4partI/slides/24PriorityQueues.pdf Support function for priority queue ''' if self.count == self.capacity: # Heap is full. Make some space. self._popLRU() self.heap[self.count] = [key, value, time] self.position[key] = self.count self.count += 1 self._swinm(self.count - 1) return # @param capacity, an integer def __init__(self, capacity): # Use min heap to do find and remove the least recent used record. self.heap = [None] * capacity # Each element: [key, value, time] self.count = 0 self.capacity = capacity # Used to store the mapping between key and the corresponding record's # position in self.heap. self.position = {} # Record the current time self.time = 0 # @param key, an integer # @return an integer def get(self, key): self.time += 1 if key not in self.position: # Not found in our db. return -1 else: # Update the used time for the record posInHeap = self.position[key] self.heap[posInHeap][2] = self.time self._sink(posInHeap) return self.heap[self.position[key]][1] # @param key, an integer # @param value, an integer # @return nothing def set(self, key, value): self.time += 1 if key not in self.position: # Add a new record. self._addNew(key, value, self.time) else: # Update the used time and value of the existing record. self.heap[self.position[key]][2] = self.time self.heap[self.position[key]][1] = value self._sink(self.position[key]) |