Python solution easy understand (accepted), include logic graph


  • 0
    M
    # Reference:
    # http://bookshadow.com/weblog/2016/11/22/leetcode-lfu-cache/ (best understanding solution)
    # 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.head = None
            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:
                    removedKeyNodeValue = self.head.last.key
                    self.unlink(self.head, self.head.last)
                    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
                        if not self.head:
                            self.head = currentFreqNode
                        else:
                            currentFreqNode.next = self.head
                            self.head.prev = currentFreqNode
                            self.head = currentFreqNode
                    self.link(currentFreqNode, currentKeyNode)
            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
            self.unlink(currentFreqNode, currentKeyNode)
            self.link(currentFreqNode.next, currentKeyNode)
    
            currentKeyNode.freq += 1
    
        def unlink(self, FreqNode, KeyNode):
            # 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):
                    self.head = None
                # When LFU's head is current freqNode, unlink keyNode means, reset head
                elif self.head == FreqNode:
                    self.head = 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
                # Delete freqNode after unlink
                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
    
        def link(self, FreqNode, KeyNode):
            if not self.head:
                self.head = FreqNode
            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('test:', myLFU.head.freq)
    # print('test:', myLFU.head.freq, myLFU.head.next.freq)
    # print('test:', myLFU.head.freq, myLFU.head.next.freq, myLFU.head.next.next.freq)
    
    # print(myLFU.head.first.value)
    # print(myLFU.head.first.value, myLFU.head.next.first.value)
    # print(myLFU.head.first.value, myLFU.head.next.first.value, myLFU.head.next.next.first.value)
    
    # 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       ]
    
    

Log in to reply
 

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