Python O(1) solution using two dictionary + double linked list

  • 1

    Inspired by @xiyayan 's solution here

    Some notes:
    keymap = { key : node }
    fremap = { fre : root }, root is circular linked list that connects to self at the beginning. Hence is the head of the list (oldest node, to be removed) and root.prev is the last (newest, to be removed)

    If it is LRU problem, we can remove fremap but only the double linked list.

    class LFUCache(object):
        def __init__(self, capacity):
            :type capacity: int
            self.cap = capacity
            self.keymap = {}
            self.fremap = {}
            self.minfre = 1
        def get(self, key):
            :type key: int
            :rtype: int
            if key not in self.keymap:
                return -1
                node = self.keymap[key]
                node.fre += 1
                if self.fremap[self.minfre].next is self.fremap[self.minfre]:
                    self.minfre += 1
                root = self.fremap.setdefault(node.fre, DoubleListNode(None, None))
                self.ddAddToTail(node, root)
                return node.value
        def put(self, key, value):
            :type key: int
            :type value: int
            :rtype: void
            if self.cap == 0: return
            if key in self.keymap:
                self.keymap[key].value = value
                if len(self.keymap) == self.cap:
                    root = self.fremap[self.minfre]
                    keytbd =
                    del self.keymap[keytbd]
                node, self.minfre = DoubleListNode(key, value), 1
                root = self.fremap.setdefault(self.minfre, DoubleListNode(None, None))
                self.ddAddToTail(node, root)
                self.keymap[key] = node
        def ddRemove(self, node):
            n1, n2 = node.prev,
  , n2.prev = n2, n1
            node.prev, = None, None
        def ddAddToTail(self, node, tail):
            n1, n2 = tail.prev, tail
            node.prev, = n1, n2
  , n2.prev = node, node
    class DoubleListNode(object):
        def __init__(self, key, value):
            self.fre = 1
            self.key = key
            self.value = value
            self.prev = self
   = self

Log in to reply

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