mirror of https://github.com/doocs/leetcode.git
89 lines
2.4 KiB
Python
89 lines
2.4 KiB
Python
class Node:
|
|
def __init__(self, key: int, value: int) -> None:
|
|
self.key = key
|
|
self.value = value
|
|
self.freq = 1
|
|
self.prev = None
|
|
self.next = None
|
|
|
|
|
|
class DoublyLinkedList:
|
|
def __init__(self) -> None:
|
|
self.head = Node(-1, -1)
|
|
self.tail = Node(-1, -1)
|
|
self.head.next = self.tail
|
|
self.tail.prev = self.head
|
|
|
|
def add_first(self, node: Node) -> None:
|
|
node.prev = self.head
|
|
node.next = self.head.next
|
|
self.head.next.prev = node
|
|
self.head.next = node
|
|
|
|
def remove(self, node: Node) -> Node:
|
|
node.next.prev = node.prev
|
|
node.prev.next = node.next
|
|
node.next, node.prev = None, None
|
|
return node
|
|
|
|
def remove_last(self) -> Node:
|
|
return self.remove(self.tail.prev)
|
|
|
|
def is_empty(self) -> bool:
|
|
return self.head.next == self.tail
|
|
|
|
|
|
class LFUCache:
|
|
def __init__(self, capacity: int):
|
|
self.capacity = capacity
|
|
self.min_freq = 0
|
|
self.map = defaultdict(Node)
|
|
self.freq_map = defaultdict(DoublyLinkedList)
|
|
|
|
def get(self, key: int) -> int:
|
|
if self.capacity == 0 or key not in self.map:
|
|
return -1
|
|
node = self.map[key]
|
|
self.incr_freq(node)
|
|
return node.value
|
|
|
|
def put(self, key: int, value: int) -> None:
|
|
if self.capacity == 0:
|
|
return
|
|
if key in self.map:
|
|
node = self.map[key]
|
|
node.value = value
|
|
self.incr_freq(node)
|
|
return
|
|
if len(self.map) == self.capacity:
|
|
ls = self.freq_map[self.min_freq]
|
|
node = ls.remove_last()
|
|
self.map.pop(node.key)
|
|
node = Node(key, value)
|
|
self.add_node(node)
|
|
self.map[key] = node
|
|
self.min_freq = 1
|
|
|
|
def incr_freq(self, node: Node) -> None:
|
|
freq = node.freq
|
|
ls = self.freq_map[freq]
|
|
ls.remove(node)
|
|
if ls.is_empty():
|
|
self.freq_map.pop(freq)
|
|
if freq == self.min_freq:
|
|
self.min_freq += 1
|
|
node.freq += 1
|
|
self.add_node(node)
|
|
|
|
def add_node(self, node: Node) -> None:
|
|
freq = node.freq
|
|
ls = self.freq_map[freq]
|
|
ls.add_first(node)
|
|
self.freq_map[freq] = ls
|
|
|
|
|
|
# Your LFUCache object will be instantiated and called as such:
|
|
# obj = LFUCache(capacity)
|
|
# param_1 = obj.get(key)
|
|
# obj.put(key,value)
|