Python O(1) solution


  • 0
    L

    use dict d for (k,v) dictionary
    use dict fd for (freq, (tail_node,head_node)) dictionary
    use ref tail for LFU tail
    use int minf for storing smallest freq

    notice: if over capacity, delete before insertion

    class Node:
        def __init__(self, key, val):
            self.key = key
            self.val = val
            self.f = 1
            self.next = None
            self.prev = None
    
        def connect(self, nextnode):
            self.next = nextnode
            if nextnode:
                nextnode.prev = self
    
    
    class LFUCache(object):
        def __init__(self, capacity):
            """
            :type capacity: int
            """
            self.cap = capacity
            self.tail = None
            self.d = {}
            self.fd = {}
            self.minf = 0
            self.size = 0
    
        def get(self, key):
            """
            :type key: int
            :rtype: int
            """
            if key not in self.d:
                return -1
            node = self.d[key]
            self.hit(node)
            return node.val
    
        def put(self, key, value):
            """
            :type key: int
            :type value: int
            :rtype: void
            """
            if self.cap == 0:
                return
            if key in self.d:
                node = self.d[key]
                self.hit(node)
                node.val = value
    
            else:
    
                self.size += 1
    
                if self.size > self.cap:
                    (tail, head) = self.fd[self.minf]
                    self.remove(tail)
                    del self.d[tail.key]
    
                    if tail.next:
                        self.tail = tail.next
    
                    self.size -= 1
    
                node = Node(key, value)
                self.d[key] = node
                if not self.tail:
                    self.tail = node
                self.moveToHead(node)
    
        def hit(self, node):
            self.remove(node)
    
            node.f += 1
    
            self.moveToHead(node)
    
            if self.tail == node:
                if node.f - 1 in self.fd:
                    self.tail = self.fd[node.f - 1][0]
                else:
                    self.tail = self.fd[node.f][0]
    
        def remove(self, node):
            f = node.f
            (ftail, fhead) = self.fd[f]
            if ftail == node:
                ftail = node.next
                if ftail:
                    ftail.prev = None
            if fhead == node:
                fhead = node.prev
                if fhead:
                    fhead.next = None
            if node.prev:
                node.prev.connect(node.next)
            if not ftail and not fhead:
                del self.fd[f]
                if f == self.minf:
                    self.minf = 0
    
            else:
                self.fd[f] = (ftail, fhead)
    
        def moveToHead(self, node):
            f = node.f
            if self.minf == 0 or f < self.minf:
                self.minf = f
            if f in self.fd:
                (ftail, fhead) = self.fd[f]
                fhead.connect(node)
            else:
                ftail = node
                node.prev = None
            node.next = None
            self.fd[f] = (ftail, node)
    
    
    
        
    
    # Your LFUCache object will be instantiated and called as such:
    # obj = LFUCache(capacity)
    # param_1 = obj.get(key)
    # obj.put(key,value)
    

Log in to reply
 

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