[Python手撕]LFU

class Node:
    def __init__(self, key=0, val=0, pre=None, next=None, fre=0, tail=None):
        self.key = key
        self.val = val
        self.pre = pre
        self.next = next
        self.fre = fre
        self.tail = tail


class LFUCache:

    def __init__(self, capacity: int):
        self.fre_to_node = {}
        self.key_to_node = {}
        self.length = 0
        self.capacity = capacity
        self.init_fre(1)

    def init_fre(self, fre):
        # 新建一个频次的链表
        head = Node()
        tail = Node()
        head.next = tail
        tail.pre = head
        self.fre_to_node[fre] = head
        self.fre_to_node[fre].tail = tail

    def insert(self, fre, node):
        # 如果下一频次的链表还不存在
        if fre not in self.fre_to_node:
            self.init_fre(fre)
        # 插入新频次链表的头部
        node.next = self.fre_to_node[fre].next
        self.fre_to_node[fre].next.pre = node
        self.fre_to_node[fre].next = node
        node.pre = self.fre_to_node[fre]
        # 更新节点的频次值
        node.fre = fre

    def remove(self, node):
        # 从双向链表中删除节点
        node.pre.next = node.next
        node.next.pre = node.pre

    def show(self):
        print("展示---------------")
        index = 1
        while index in self.fre_to_node:
            print("频率", index)
            cur = self.fre_to_node[index].next
            while cur != self.fre_to_node[index].tail:
                print(cur.val, end="->")
                cur = cur.next
            print()
            index += 1
        print("键集合", self.key_to_node.keys())
        print("结束---------------")

    def get(self, key: int) -> int:
        # 如果键不存在
        if key not in self.key_to_node:
            return -1
        else:
            # 如果键存在，把这个节点更新到下一频次
            node = self.key_to_node[key]
            self.remove(node)
            self.insert(node.fre + 1, node)
            return node.val

    def put(self, key: int, value: int) -> None:
        # 如果键不存在
        if key not in self.key_to_node:
            # LFU未满
            if self.length < self.capacity:
                node = Node(key=key, val=value, fre=1)
                self.insert(1, node)
                self.key_to_node[key] = node
                self.length += 1
            else:
                # LFU已满
                index = 1
                while index in self.fre_to_node:
                    if self.fre_to_node[index].next != self.fre_to_node[index].tail:
                        break
                    index += 1
                t = self.fre_to_node[index].tail.pre
                del self.key_to_node[t.key]
                self.remove(t)

                node = Node(key=key, val=value, fre=1)
                self.insert(1, node)
                self.key_to_node[key] = node
        else:
            # 如果键存在，只需要更新键值，把节点更新到下一频次
            node = self.key_to_node[key]
            node.val = value
            self.remove(node)
            self.insert(node.fre + 1, node)


# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)