请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。

实现 LFUCache 类：

• LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
• int get(int key) - 如果键存在于缓存中，则获取键的值，否则返回 -1。
• void put(int key, int value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最久未使用 的键。

注意「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。

进阶：

• 你是否可以在 O(1) 时间复杂度内执行两项操作？

示例：

输入：
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
输出：
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

解释：
LFUCache lFUCache = new LFUCache(2);
lFUCache.put(1, 1);
lFUCache.put(2, 2);
lFUCache.get(1);      // 返回 1
lFUCache.put(3, 3);   // 去除键 2
lFUCache.get(2);      // 返回 -1（未找到）
lFUCache.get(3);      // 返回 3
lFUCache.put(4, 4);   // 去除键 1
lFUCache.get(1);      // 返回 -1（未找到）
lFUCache.get(3);      // 返回 3
lFUCache.get(4);      // 返回 4

提示：

• 0 <= capacity, key, value <= 104
• 最多调用 105 次 get 和 put 方法

Solution

参考题解：@王尼玛

• 两个哈希表 + N个双链表

• key-node 哈希表、freq-LinkedList 哈希表

# @lc code=start
class Node:
    def __init__(self, key=None, value=None, freq=0):
        self.key=key
        self.value=value
        self.freq=freq
        self.prev=None
        self.next=None

class LinkedList:
    def __init__(self):
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def insertFirst(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
        
    def delete(self, node):
        if self.isEmpty():
            return
        node.prev.next = node.next
        node.next.prev = node.prev
        node.next = None
        node.prev = None
        
    def getLast(self):
        if self.isEmpty():
            return None
        return self.tail.prev
    
    def isEmpty(self):
        return self.head.next==self.tail
        
class LFUCache:

    def __init__(self, capacity: int):
        """[summary]

        Args:
            capacity (int): [缓存最大容量]
            keyMap (dict): [key->Node]
            freqMap (dict): [freq->LinkedList]
            minFreq (int): [缓存中的最低频率]
        """
        self.capacity=capacity
        self.keyMap = dict()
        self.freqMap = dict()
        self.minFreq = 0

    def get(self, key: int) -> int:
        if key not in self.keyMap:
            return -1
        node = self.keyMap[key]
        self.increaseFreq(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.keyMap:
            node = self.keyMap[key]
            node.value = value
            self.increaseFreq(node)
        else:
            if self.capacity==0:
                return
            if len(self.keyMap)==self.capacity:
                self.removeMinFreq()
            node = Node(key, value, 1)
            self.increaseFreq(node, True)
            self.keyMap[key] = node

    def increaseFreq(self, node, isNew=False):
        """[更新节点的访问频率]
        Args:
            node (Node): [待更新的节点]
            isNew (bool): [是否为新节点]
        """
        if isNew:
            self.minFreq = 1
            self.setLinkedList(node)
        else:
            self.delNode(node)
            node.freq += 1
            self.setLinkedList(node)
            if self.minFreq not in self.freqMap:
                self.minFreq += 1
                
    def setLinkedList(self, node):
        """[根据节点的频率，插入到对应的LinkedList中，如果LinkedList不存在则创建]

        Args:
            node ([Node]): [待插入的节点]
        """
        if node.freq not in self.freqMap:
            self.freqMap[node.freq]=LinkedList()
        linkedList = self.freqMap[node.freq]
        linkedList.insertFirst(node)
        
    def delNode(self, node):
        """[删除指定的节点，如果节点删除后，对应的双链表为空，则从freqMap中删除这个链表]

        Args:
            node ([Node]): [待删除的节点]
        """
        if node.freq not in self.freqMap:
            return 
        linkedList = self.freqMap[node.freq]
        linkedList.delete(node)
        if linkedList.isEmpty():
            del self.freqMap[node.freq]
            
    def removeMinFreq(self):
        """
        删除频率最低的元素，从freqMap和keyMap中都要删除这个节点，
        如果节点删除后对应的链表为空，则要从freqMap中删除这个链表
        """
        linkedList = self.freqMap[self.minFreq]
        node = linkedList.getLast()
        linkedList.delete(node)
        del self.keyMap[node.key]
        if linkedList.isEmpty():
            del self.freqMap[node.freq]

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