设计LFU缓存结构

设计LFU缓存结构_牛客题霸_牛客网

问题简述

设计LFU(最近最少频次使用)缓存结构。

思路

• 定义 key2cnt 保存 key 的操作频数；cnt2key 保存各频数的 key 队列；

  • cnt2key 中可以使用 dict（只使用 key）作为有序 set 代替队列，提升删除效率；

• 定义 refresh，每次操作后更新 cnt 队列；

• 定义 least 保存当前最少的频数；

  • 每次有新 key 进来时，重置 least 为 1；

  • 每次更新 cnt2key 后，如果当前的队列为空且等于 least，需要least += 1；

Python 写法1

class Solution:
    from collections import defaultdict, deque
    k: int  # 容量
    least = 1  # 记录当前最少频次
    key2val = dict()
    key2cnt = defaultdict(int)  # 这个和 key2val 可以合并在一起可以省一组 key，这里为了更清晰分开存储
    cnt2key = defaultdict(dict)  # 这里实际只用到了 dict 的 key 作为有序 set
    
    def refresh(self, key):
        cnt = self.key2cnt[key]
        self.cnt2key[cnt].pop(key)
        if len(self.cnt2key[cnt]) == 0:
            self.cnt2key.pop(cnt)
            if self.least == cnt:
                self.least += 1
        self.key2cnt[key] += 1
        self.cnt2key[cnt + 1][key] = None  # 因为只用了 key，
    
    def get(self, key):
        ret = self.key2val.get(key, -1)
        if key in self.key2val:
            self.refresh(key)
        return ret
        
    def set(self, key, value):
        if key not in self.key2val:
            # 超容量的情况
            if len(self.key2val) >= self.k:
                tmp = next(iter(self.cnt2key[self.least]))
                # 全部 pop
                self.cnt2key[self.least].pop(tmp)
                self.key2val.pop(tmp)
                self.key2cnt.pop(tmp)
            self.key2val[key] = value
            self.key2cnt[key] += 1
            self.cnt2key[self.key2cnt[key]][key] = None
            self.least = 1  # 因为是新的 key，所以显然最少频次将更新为 1
        else:
            self.refresh(key)
            self.key2val[key] = value
    
    def LFU(self , operators: List[List[int]], k: int) -> List[int]:
        self.k = k
        
        ret = []
        for op in operators:
            if op[0] == 1:
                self.set(op[1], op[2])
            else:
                ret.append(self.get(op[1]))
        
        return ret

• 写法 2 的区别仅在于将 key2cnt 和 key2val 合并在一起，省了一组 key 的空间；

Python 写法2

class Solution:
    from collections import defaultdict, deque
    k: int  # 容量
    least = 1  # 记录当前最少频次
    key2cnt = dict()  # 出了保存频次，也保存了值
    cnt2key = defaultdict(dict)  # 这里实际只用到了 dict 的 key 作为有序 set
    # 这里也可以使用队列，但是删除效率应该不如 set
    
    def refresh(self, key):
        cnt = self.key2cnt[key][0]
        self.cnt2key[cnt].pop(key)
        if len(self.cnt2key[cnt]) == 0:
            self.cnt2key.pop(cnt)
            if self.least == cnt:
                self.least += 1
        self.key2cnt[key][0] += 1
        self.cnt2key[cnt + 1][key] = None  # 因为只用了 key，
    
    def get(self, key):
        ret = self.key2cnt[key][1] if key in self.key2cnt else -1
        if key in self.key2cnt:
            self.refresh(key)
        return ret
        
    def set(self, key, value):
        if key not in self.key2cnt:
            # 超容量的情况
            if len(self.key2cnt) >= self.k:
                tmp = next(iter(self.cnt2key[self.least]))
                # 全部 pop
                self.cnt2key[self.least].pop(tmp)
                self.key2cnt.pop(tmp)
            cnt = 1
            self.key2cnt[key] = [cnt, value]
            self.cnt2key[cnt][key] = None
            self.least = 1  # 因为是新的 key，所以显然最少频次将更新为 1
        else:
            self.refresh(key)
            self.key2cnt[key][1] = value
    
    def LFU(self , operators: List[List[int]], k: int) -> List[int]:
        self.k = k
        
        ret = []
        for op in operators:
            if op[0] == 1:
                self.set(op[1], op[2])
            else:
                ret.append(self.get(op[1]))
        
        return ret