class Node:
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.freq = 1
self.prev = None
self.next = None
class LFUCache(object):
def __init__(self, capacity):
"""
:type capacity: int
"""
self.capacity = capacity
self.key_to_node = {}
def linked_list():
dummy = Node()
dummy.prev = dummy
dummy.next = dummy
return dummy
self.freq_to_dummy = collections.defaultdict(linked_list)
def get_node(self, key):
if key not in self.key_to_node:
return None
node = self.key_to_node[key]
self.remove(node)
dummy = self.freq_to_dummy[node.freq]
if dummy.prev == dummy:
del self.freq_to_dummy[node.freq]
if self.min_freq == node.freq:
self.min_freq += 1
node.freq += 1
self.push_front(self.freq_to_dummy[node.freq], node)
return node
def remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def push_front(self, dummy, node):
node.prev = dummy
node.next = dummy.next
node.prev.next = node
node.next.prev = node
def get(self, key):
"""
:type key: int
:rtype: int
"""
node = self.get_node(key)
return node.value if node else -1
def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: None
"""
node = self.get_node(key)
if node:
node.value = value
return
if len(self.key_to_node) == self.capacity:
dummy = self.freq_to_dummy[self.min_freq]
back_node = dummy.prev
del self.key_to_node[back_node.key]
self.remove(back_node)
if dummy.prev == dummy:
del self.freq_to_dummy[self.min_freq]
new_node = Node(key, value)
self.key_to_node[key] = new_node
self.push_front(self.freq_to_dummy[1], new_node)
self.min_freq = 1
# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)