本文共 2124 字，大约阅读时间需要 7 分钟。

class Node:    def __init__(self, key=-1, val=-1):        self.key = key        self.val = val        self.freq = 1        self.prev = None        self.next = Noneclass DLinkedList:    def __init__(self):        self.head = Node()        self.tail = Node()        self.head.next = self.tail        self.tail.prev = self.head        self.size = 0    def addToHead(self, node):        node.prev = self.head        node.next = self.head.next        self.head.next = node        node.next.prev = node        self.size += 1    def removeNode(self, node):        node.prev.next = node.next        node.next.prev = node.prev        self.size -= 1    def removeTail(self):        node = self.tail.prev        self.removeNode(node)        return nodefrom collections import defaultdictclass LFUCache:    def __init__(self, capacity: int):        self.cache = {   }        self.freq = defaultdict(DLinkedList)        self.size = 0        self.capacity = capacity        self.min_freq = 0    def get(self, key: int) -> int:        if key in self.cache:            node = self.cache[key]            self.freq[node.freq].removeNode(node)            if self.min_freq == node.freq and self.freq[node.freq].size == 0:                self.min_freq += 1            node.freq += 1            self.freq[node.freq].addToHead(node)              return node.val        return -1    def put(self, key: int, value: int) -> None:        if self.capacity == 0:            return        if key in self.cache:            node = self.cache[key]            node.val = value            self.freq[node.freq].removeNode(node)            if self.min_freq == node.freq and self.freq[node.freq].size == 0:                self.min_freq += 1            node.freq += 1            self.freq[node.freq].addToHead(node)        else:            self.size += 1            if self.size > self.capacity:                node = self.freq[self.min_freq].removeTail()                self.cache.pop(node.key)                self.size -= 1            node = Node(key, value)            self.cache[key] = node            self.freq[1].addToHead(node)            self.min_freq = 1