题解 | #设计LFU缓存结构#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# lfu design
# @param operators int整型二维数组 ops
# @param k int整型 the k
# @return int整型一维数组
#
class Cache:                                                                   # 设计lfu cache
    def __init__(self,cap):
        self.cap=cap
        self.dic=dict()
    
    def isFull(self):
        return len(self.dic)==self.cap
    
    def getFirstKey(self):
        k=sorted(self.dic.items(),key=lambda x:[x[1][1],x[1][2]])[0][0]
        return k
    
    def set(self,key,val,cnt,in_order):
        if not self.isFull():
            if key not in self.dic:
                self.dic[key]=[val,1,in_order]
            else:
                self.dic[key]=[val,cnt+1,in_order]
        else:
            if key in self.dic:
                self.dic[key]=[val,cnt+1,in_order]           
            else:
                self.dic.pop(self.getFirstKey())
                self.dic[key]=[val,1,in_order]
                
    def get(self,key,in_order):
        if key  in self.dic:
            self.dic[key][1]+=1
            self.dic[key][2]=in_order
            return self.dic[key][0]
        else:
            return -1
                
    
class Solution:
    def LFU(self , operators: List[List[int]], k: int) -> List[int]:
        res=[]
        cache=Cache(k)                                    # 使用cache，传入大小
        cnt=0                                                     # 用cnt统计次数（频率）
        for i in range(len(operators)):                # 用 i 体现元素进入的先后
            if operators[i][0]==1:
                cache.set(operators[i][1],operators[i][2],cnt,i)
            if operators[i][0]==2:
                res.append(cache.get(operators[i][1],i))
        return res