# Python solution easy understand (accepted), include logic graph

• ``````# Reference:
# After read and understand the referenced article, I re-wrote this whole scripts (my solution is faster then the reference)
# Logic Graph：
# LFU Cache ---> FreqNode1 (head) ---- FreqNode2 ---- ... ---- FreqNodeN
#                    |                     |                       |
#                 KeyNodeA (first)      KeyNodeE (first)        KeyNodeG (first)
#                    |                     |                       |
#                 KeyNodeB              KeyNodeF (last)         KeyNodeH
#                    |                                             |
#                 KeyNodeC                                      KeyNodeI (last)
#                    |
#                 KeyNodeD (last)
#
# FreqNode store in {freqDict}
# KeyNodeE store in {keyDict}

class KeyNode(object):
def __init__(self, key, value, freq=1):
self.key = key
self.value = value
self.freq = freq
self.prev = self.next = None

class FreqNode(object):
def __init__(self, freq):
self.freq = freq
self.prev = self.next = None
self.first = self.last = None

class LFUCache(object):
def __init__(self, capacity):
self.capacity = capacity
self.freqDict = dict()  # freqDict = {freq:FreqNode}
self.keyDict = dict()  # keyDict = {key:KeyNode}

def get(self, key):
if key in self.keyDict:
keyNode = self.keyDict[key]
nodeValue = keyNode.value
self.increase(key)
return nodeValue
else:
return -1

def put(self, key, value):
if self.capacity == 0:
return None

if key not in self.keyDict:
if len(self.keyDict) == self.capacity:
self.keyDict.pop(removedKeyNodeValue)
self.put(key, value)
else:
self.keyDict[key] = KeyNode(key, value)
currentKeyNode = self.keyDict.get(key)
if 1 in self.freqDict:
currentFreqNode = self.freqDict.get(1)
else:
newFreqNode = FreqNode(1)
self.freqDict[1] = newFreqNode
currentFreqNode = self.freqDict.get(1)
# First time put
else:
else:
currentKeyNode = self.keyDict.get(key)
currentKeyNode.value = value
self.increase(key)

def increase(self, key):
currentKeyNode = self.keyDict.get(key)
currentKeyNodeFreq = currentKeyNode.freq

currentFreqNode = self.freqDict.get(currentKeyNodeFreq)
currentFreqNodeFreq = currentFreqNode.freq

if currentFreqNode.next == None or currentFreqNodeFreq + 1 < currentFreqNode.next.freq:
newFreqNode = FreqNode(currentFreqNodeFreq + 1)
newFreqNode.next = currentFreqNode.next
newFreqNode.prev = currentFreqNode
if currentFreqNode.next:
currentFreqNode.next.prev = newFreqNode
currentFreqNode.next = newFreqNode
self.freqDict[newFreqNode.freq] = newFreqNode

currentKeyNode.freq += 1

# When there is only one keyNode in freqNode, after unlink keyNode and freqNode, delete freqNode
if FreqNode.first == KeyNode and FreqNode.last == KeyNode:
# When capacity is 1 or only one FreqNode in LFU cache
if self.capacity == 1 or (self.head == FreqNode and not FreqNode.next):
FreqNode.next.prev = None
# When LFU's last freqNode is current freqNode, remove it
elif FreqNode.next == None:
FreqNode.prev.next = None
# When current freqNode is middle of LFU, remove it
else:
currentFreqNodeNext = FreqNode.next
currentFreqNodePrev = FreqNode.prev
FreqNode.prev.next = currentFreqNodeNext
FreqNode.next.prev = currentFreqNodePrev
self.freqDict.pop(FreqNode.freq)
# When there is more than two keyNodes in freqNode, unlink keyNode from freqNode but keep freqNode
# When keyNode is first
elif FreqNode.first == KeyNode and FreqNode.last != KeyNode:
FreqNode.first = KeyNode.next
KeyNode.next.prev = None
# When keyNode is not first and last
elif FreqNode.first != KeyNode and FreqNode.last != KeyNode:
currentKeyNodeNext = KeyNode.next
currentKeyNodePrev = KeyNode.prev
KeyNode.prev.next = currentKeyNodeNext
KeyNode.next.prev = currentKeyNodePrev
# When keyNode is last
else:
FreqNode.last = KeyNode.prev
KeyNode.prev.next = None

if FreqNode.first == None and FreqNode.last == None:
FreqNode.first = FreqNode.last = KeyNode
else:
KeyNode.next = FreqNode.first
FreqNode.first.prev = KeyNode
FreqNode.first = KeyNode

myLFU = LFUCache(1)
myLFU.put(2, 1)
print(myLFU.get(2))
myLFU.put(3, 2)
myLFU.get(2)
myLFU.get(3)

# print(myLFU.keyDict)
# print(myLFU.freqDict[3].prev)

# print(myLFU.freqDict[myLFU.keyDict[3].freq].freq)
# ["LFUCache",  "put",  "put",  "get",  "get",  "get",  "put",  "put",  "get",  "get",  "get",  "get"   ]

# [[3],         [2,2],  [1,1],  [2],    [1],    [2],    [3,3],  [4,4],  [3],    [2],    [1],    [4]     ]
# [null,        null,   null,   2,      1,      2,      null,   null,   -1,     2,      1,      4       ]

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.