Ugly implementation


  • 0
    Z

    I use two hash map and one doubly linked list, one map maintains the most frequent used item, so we know where to append the new item has the same frequency.

    class Node(object):
        def __init__(self, val, key, frequency):
            self.val = val
            self.key = key
            self.frequency = frequency
            self.next = None
            self.prev = None
    
    class LFUCache(object):
    
        def __init__(self, capacity):
            """
            :type capacity: int
            """
            self.head = None
            self.capacity = capacity
            self.data_map = {}
            # pointing to the most recent used node for the same frequency
            self.recent_used = {}
    
        def get(self, key):
            if key not in self.data_map:
                return -1
            node = self.data_map[key]
            if node.frequency in self.recent_used and node is self.recent_used[node.frequency]:
                if node.prev and node.prev.frequency == node.frequency:
                    self.recent_used[node.frequency] = node.prev
                else:
                    del self.recent_used[node.frequency]
            frequency = node.frequency
            node.frequency += 1
            if frequency in self.recent_used and self.recent_used[frequency] is not node or frequency + 1 in self.recent_used:
                if frequency + 1 in self.recent_used:
                    frequency += 1
                # remove node and add it back
                if node.prev:
                    node.prev.next = node.next
                # node is head
                else:
                    self.head = node.next
                if node.next:
                    node.next.prev = node.prev
                node.prev = self.recent_used[frequency]
                node.next = node.prev.next
                node.prev.next = node
                if node.next:
                    node.next.prev = node
            self.recent_used[node.frequency] = node
            return node.val
    
        def put(self, key, value):
            if self.capacity == 0:
                return
            if key not in self.data_map:
                if len(self.data_map) == self.capacity:
                    self.remove()
                node = Node(value, key, 0)
                # add new node
                self.data_map[key] = node
                if 0 in self.recent_used:
                    node.prev = self.recent_used[0]
                    node.next = node.prev.next
                    node.prev.next = node
                    if node.next:
                        node.next.prev = node
                else:
                    node.next = self.head
                    if self.head:
                        self.head.prev = node
                    self.head = node
                self.recent_used[0] = node
            # key already in map
            else:
                node = self.data_map[key]
                node.val = value
                self.get(key)
        
        def remove(self):
            # node is head
            node = self.head
            self.head = self.head.next
            if self.head:
                self.head.prev = None
            if node.frequency in self.recent_used and node is self.recent_used[node.frequency]:
                del self.recent_used[node.frequency]
            del self.data_map[node.key]
    

Log in to reply
 

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