Generalized approach (can solve follow-ups and 460. LFU Cache): doubly linked list of doubly linked list (Python, explained)

• Doubly linked list of doubly linked list with two corresponding hash tables:
key:keyNode, count:countNode.

Both keyNode and countNode inherit from DoublyListNode.

To illustrate, consider case (key:count): 'a':4, 'b':2, 'c':2, 'd':1

``````CountNode(1) - KeyNode('d')
|
CountNode(2) - KeyNode('b') - KeyNode('c')
|
CountNode(4) - KeyNode('a')
``````

We highlight that doubly linked list of doubly linked list is a generalized approach. It can deal with follow-ups: if there are multiple maxKeys or minKeys, return the most/least recently used key instead of any key.

For example:

1. LFU Cache https://leetcode.com/problems/lfu-cache/

can be solved in a similar way.

Create or delete keyNode, countNode and update dicts properly. Details are in the comments of the code.

``````class DoublyListNode(object):
def __init__(self, count):
self.count = count
self.prev = None
self.next = None

class KeyNode(DoublyListNode):
def __init__(self, count, key):
super(KeyNode, self).__init__(count)
self.key = key

class CountNode(DoublyListNode):
def __init__(self, count):
super(CountNode, self).__init__(count)
self.fakeTail = KeyNode(0, '#')

class AllOne(object):
def __init__(self):
"""
"""
self.fakeTail = CountNode(0)

self.keyNode = dict()
self.countNode = dict()

def inc(self, key):
"""
Inserts a new key <Key> with value 1. Or increments an existing key by 1.
:type key: str
:rtype: void
"""
# Depending on whether key exists, we have different newCount and oldCountNode.
keyNodeRemoved = False
if key in self.keyNode:
oldKeyNode = self.keyNode[key]
newCount = oldKeyNode.count + 1
oldCountNode = self.countNode[oldKeyNode.count]
self.removeNode(oldKeyNode)
keyNodeRemoved = True
else:
newCount = 1
newKeyNode = KeyNode(newCount, key)
self.keyNode[key] = newKeyNode

if newCount in self.countNode:
# If newCount does not have a countNode, create a new CountNode.
else:
newCountNode = CountNode(newCount)
self.insertNode(oldCountNode, newCountNode)
self.countNode[newCount] = newCountNode

# If a keyNode is removed and this count corresponds to no key, remove this countNode.
if keyNodeRemoved and oldCountNode.fakeHead.next is oldCountNode.fakeTail:
del self.countNode[oldCountNode.count]
self.removeNode(oldCountNode)

def dec(self, key):
"""
Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
:type key: str
:rtype: void
"""
if key not in self.keyNode:
return

# Get newCount and oldCountNode.
oldKeyNode = self.keyNode[key]
newCount = oldKeyNode.count - 1
oldCountNode = self.countNode[oldKeyNode.count]
self.removeNode(oldKeyNode)

if newCount > 0:
newKeyNode = KeyNode(newCount, key)
self.keyNode[key] = newKeyNode
if newCount in self.countNode:
# If newCount does not have a countNode, create a new CountNode.
else:
newCountNode = CountNode(newCount)
self.insertNode(oldCountNode.prev, newCountNode)
self.countNode[newCount] = newCountNode
else:
del self.keyNode[key]

# If a keyNode is removed and this count corresponds to no key, remove this countNode.
del self.countNode[oldCountNode.count]
self.removeNode(oldCountNode)

def getMaxKey(self):
"""
Returns one of the keys with maximal value.
:rtype: str
"""
return ''
else:

def getMinKey(self):
"""
Returns one of the keys with Minimal value.
:rtype: str
"""
return ''
else:

def removeNode(self, node):
node.prev.next = node.next
node.next.prev = node.prev

def insertNode(self, prevNode, node):
nextNode = prevNode.next
node.prev = prevNode
node.next = nextNode
prevNode.next = node
nextNode.prev = node
``````

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