题解 | 设计LFU缓存结构

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# lfu design
# @param operators int整型二维数组 ops
# @param k int整型 the k
# @return int整型一维数组
#
from typing import List
from collections import OrderedDict

class Solution:
    def LFU(self, operators: List[List[int]], k: int) -> List[int]:
        # 初始化缓存容量
        self.capacity = k
        # 存储键到 (值, 访问频率) 的映射
        self.key_dict = {}
        # 存储访问频率到对应的键的映射
        self.freq_dict = {}
        # 记录当前最小的访问频率
        self.min_freq = 0
        result = []
        for op in operators:
            if op[0] == 1:
                # 插入或更新键值对
                self.set(op[1], op[2])
            elif op[0] == 2:
                # 获取键对应的值
                result.append(self.get(op[1]))
        return result

    def get(self, key):
        if key not in self.key_dict:
            return -1
        # 获取键对应的值和频率
        value, freq = self.key_dict[key]
        # 从当前频率对应的有序字典中移除该键
        self.freq_dict[freq].pop(key)
        if not self.freq_dict[freq]:
            # 如果当前频率对应的有序字典为空，删除该频率的记录
            del self.freq_dict[freq]
            if self.min_freq == freq:
                # 如果当前最小频率的记录为空，更新最小频率
                self.min_freq = min(self.freq_dict.keys()) if self.freq_dict else 0
        # 访问频率加 1
        freq += 1
        if freq not in self.freq_dict:
            # 如果新的频率不存在，创建一个新的有序字典
            self.freq_dict[freq] = OrderedDict()
        # 将键添加到新的频率对应的有序字典中
        self.freq_dict[freq][key] = 1
        # 更新键对应的频率
        self.key_dict[key] = (value, freq)
        return value

    def set(self, key, value):
        if self.capacity <= 0:
            return
        if key in self.key_dict:
            # 如果键已经存在，更新值并增加访问频率
            self.key_dict[key] = (value, self.key_dict[key][1])
            self.get(key)
            return
        if len(self.key_dict) >= self.capacity:
            # 如果缓存已满，淘汰访问频率最低且最久未使用的元素
            min_freq_keys = self.freq_dict[self.min_freq]
            evict_key = next(iter(min_freq_keys))
            del self.key_dict[evict_key]
            del self.freq_dict[self.min_freq][evict_key]
            if not self.freq_dict[self.min_freq]:
                del self.freq_dict[self.min_freq]
        # 插入新的键值对，初始访问频率为 1
        self.min_freq = 1
        if 1 not in self.freq_dict:
            self.freq_dict[1] = OrderedDict()
        self.freq_dict[1][key] = 1
        self.key_dict[key] = (value, 1)