首页 > 试题广场 >

设计LFU缓存结构

[编程题]设计LFU缓存结构
  • 热度指数：25689 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
一个缓存结构需要实现如下功能。
  • set(key, value)：将记录(key, value)插入该结构
  • get(key)：返回key对应的value值
但是缓存结构中最多放K条记录，如果新的第K+1条记录要加入，就需要根据策略删掉一条记录，然后才能把新记录加入。这个策略为：在缓存结构的K条记录中，哪一个key从进入缓存结构的时刻开始，被调用set或者get的次数最少，就删掉这个key的记录；
如果调用次数最少的key有多个，上次调用发生最早的key被删除
这就是LFU缓存替换算法。实现这个结构，K作为参数给出

数据范围：，
要求：get和set的时间复杂度都是 ，空间复杂度是


若opt=1，接下来两个整数x, y，表示set(x, y)
若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1

对于每个操作2，返回一个答案
示例1

输入

[[1,1,1],[1,2,2],[1,3,2],[1,2,4],[1,3,5],[2,2],[1,4,4],[2,1]],3

输出

[4,-1]

说明

在执行"1 4 4"后，"1 1 1"被删除。因此第二次询问的答案为-1

备注:

算法知识视频讲解
添加回答
Python 3
在喝茶的小鱼干很苦闷头像 在喝茶的小鱼干很苦闷 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# lfu design
# @param operators int整型二维数组 ops
# @param k int整型 the k
# @return int整型一维数组
#
class Solution:
    def LFU(self, operators: List[List[int]], k: int) -> List[int]:
        # write code here
        self.capacity = k
        self.dic = {}
        self.times = {}
        ans = []

        def pop():
            t = min(self.times)
            e = self.times[t].pop(0)
            if not self.times[t]:
                del self.times[t]
            return e

        def change(key: int, t: int):
            self.times[t].remove(key)
            if not self.times[t]:
                del self.times[t]
            if (t + 1) in self.times:
                self.times[t + 1].append(key)
            else:
                self.times[t + 1] = [key]

        def insert(key: int):
            if 1 in self.times:
                self.times[1].append(key)
            else:
                self.times[1] = [key]

        def get(key: int) -> int:
            if key in self.dic:
                change(key, self.dic[key]["times"])
                self.dic[key]["times"] += 1
                return self.dic[key]["val"]
            else:
                return -1

        def set(key: int, value: int) -> None:
            if key in self.dic:
                self.dic[key]["val"] = value
                change(key, self.dic[key]["times"])
                self.dic[key]["times"] += 1
            else:
                if len(self.dic) == self.capacity:
                    del self.dic[pop()]
            self.dic[key] = {"val": value, "times": 1}
            insert(key)

        for op in operators:
            if op[0] == 1:
                set(op[1], op[2])
            else:
                ans.append(get(op[1]))
        return ans

发表于 2024-07-17 17:12:50 回复(0)
Python 3
今天该收到offer了吧头像 今天该收到offer了吧
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# lfu design
# @param operators int整型二维数组 ops
# @param k int整型 the k
# @return int整型一维数组
#
class Solution:
    def LFU(self, operators: List[List[int]], k: int) -> List[int]:
        # write code here
        dic_val = {}
        dic_num = {} #当前值的访问次数，和访问顺序 key->int: value->[次数，顺序]
        res = []
        for i, ope in enumerate(operators):

            if ope[0] == 1:
                if len(dic_val) == k:
                    if ope[1] not in dic_val.keys():
                        key = sorted(dic_num.items(), key=lambda x: (x[1][0], x[1][1]))
                        dic_num.pop(key[0][0])
                        dic_val.pop(key[0][0])
                dic_val[ope[1]] = ope[2]
               
                if ope[1] in dic_num.keys():
                    dic_num[ope[1]] = [dic_num[ope[1]][0] + 1, i]
                else:
                    dic_num[ope[1]] = [1, i]
            else:
                if  ope[1] in dic_val.keys():
                    res.append(dic_val[ope[1]] )
                    if ope[1] in dic_num.keys():
                        dic_num[ope[1]] = [dic_num[ope[1]][0] + 1, i]
                    else:
                        dic_num[ope[1]] = [1, i]
                else:
                    res.append(-1)

        return res

发表于 2023-10-07 15:25:34 回复(0)
Python 3
taxueguilai头像 taxueguilai 
class Solution:
    def __init__(self) -> None:
        self.dic = {}

    def get_key(self):
        # 根据操作个数和tp的值对key进行排序，得到最不常用的key
        key = sorted(self.dic.items(), key=lambda x: (x[1][1], x[1][2]))[0][0]
        return key

    def get(self, key, tp):
        val = self.dic.get(key, None)
        if val != None:
            self.dic[key][1] += 1
            self.dic[key][2] = tp
            return val[0]
        else:
            return -1

    # 巧妙的使用 tp 来解决个数相等时的先后问题
    def set(self, key, val, tp):
        if key in self.dic.keys():
            self.dic[key][0] = val
            self.dic[key][1] += 1
            self.dic[key][2] = tp
        else:
            if len(self.dic.keys()) == self.size:
                self.dic.pop(self.get_key())
            self.dic[key] = [val, 1, tp]

    def LFU(self, operators: List[List[int]], k: int) -> List[int]:
        # write code here
        result = []
        self.size = k
        for i in range(len(operators)):
            if operators[i][0] == 1:
                self.set(operators[i][1], operators[i][2], i)
            else:
                res = self.get(operators[i][1], i)
                result.append(res)
        return result

发表于 2023-07-19 23:32:38 回复(0)
Python 3
收心碎的找工作er头像 收心碎的找工作er 
    def LFU(self , operators: List[List[int]], k: int) -> List[int]:
        # write code here
        result = []
        record = []
        recordkv = dict()
        recordnum = 0
        flag = 0
        if operators == None:
            return result
        for op in operators:   
            if op[0] == 1:
                if flag >= k :
                   del recordkv[record[0]]
                   record.pop(0) 
                   flag -= 1
                recordkv[op[1]] = op[2]
                if op[1] in record:
                    record.remove(op[1])
                record.append(op[1])
                flag += 1
                
            if op[0] == 2:
                if op[1] not in record:
                    result.append(-1)
                else:
                    result.append(recordkv[op[1]])
                    record.remove(op[1])
                    record.append(op[1])
                    #print(record)
        return resul

有一个用例不过，最后一个用例？帮忙看下大神

发表于 2023-05-26 18:14:21 回复(0)
Python 3
英俊的嘟教授上岸了头像 英俊的嘟教授上岸了 
from typing import List


class Solution:
    def LFU(self , operators: List[List[int]], k: int) -> List[int]:
        one_dict = {}
        two_dict = {}
        res = []
        if not operators:
            return res
        for three_int in operators:
            if three_int[0] == 1:
                self.set(three_int[1], three_int[2], k, one_dict, two_dict)
            else:
                res_t = self.get((three_int[1]), one_dict, two_dict, res)
        return res
    def set(self, key:int, value:int, k:int, dict_one, dict_two):
        # 已满
        if len(dict_one) == k:
            # 已存在，不需要删除
            if key in dict_one.keys():
                next_key = dict_one[key]
                for key_val in dict_two[next_key]:
                    if key_val[0] == key:
                        object = [key, key_val[1]]
                        dict_two[next_key].remove(object)
                        if not dict_two[next_key]:
                            dict_two.pop(next_key)
                        object = [key, value]
                        dict_one[key] += 1
                        if next_key+1 in dict_two.keys():
                            dict_two[next_key+1].append(object)
                        else:
                            dict_two[next_key+1] = [object]
                        break
            # 不存在，需要删除
            else:
                # 先找到当前要删除的key value
                for i in range(1, len(dict_one)):
                    if i in dict_two.keys():
                        pop_node = dict_two[i].pop(0)
                        pop_key = pop_node[0]
                        dict_one.pop(pop_key)
                        break
                dict_one[key] = 1
                if 1 in dict_two.keys():
                    dict_two[1].append([key, value])
                else:
                    dict_two[1] = [[key, value]]
        # 未满
        else:
            # 已存在
            if key in dict_one.keys():
                next_key = dict_one[key]
                for key_val in dict_two[next_key]:
                    if key_val[0] == key:
                        object = [key, key_val[1]]
                        dict_two[next_key].remove(object)
                        if not dict_two[next_key]:
                            dict_two.pop(next_key)
                        object = [key, value]
                        dict_one[key] += 1
                        if next_key + 1 in dict_two.keys():
                            dict_two[next_key + 1].append(object)
                        else:
                            dict_two[next_key + 1] = [object]
                        break
            # 不存在
            else:
                dict_one[key] = 1
                if 1 in dict_two.keys():
                    dict_two[1].append([key, value])
                else:
                    dict_two[1] = [[key, value]]

    def get(self, key:int, dict_one, dict_two ,res) -> int:
        if key in dict_one.keys():
            next_key = dict_one[key]
            for key_val in dict_two[next_key]:
                if key_val[0] == key:
                    val = key_val[1]
                    object = [key, val]
                    dict_two[next_key].remove(object)
                    if not dict_two[next_key]:
                        dict_two.pop(next_key)
                    dict_one[key] += 1
                    if next_key + 1 in dict_two.keys():
                        dict_two[next_key + 1].append(object)
                    else:
                        dict_two[next_key + 1] = [object]
                    res.append(val)
                    break
        else:
            res.append(-1)

发表于 2022-08-06 11:10:48 回复(0)
Python 3
东方佑头像 东方佑 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# lfu design
# @param operators int整型二维数组 ops
# @param k int整型 the k
# @return int整型一维数组
#
class Solution:
    def LFU(self , operators: List[List[int]], k: int) -> List[int]:
        # write code here

        self.capacity=k
        self.capacity_data=dict()
        self.key_list=[]
        get_res=[]
        for i in operators:
            if len(i)>=3:
                self.set(i[1],i[2])
            else:
                val=self.get(i[1])
#                 print(i[1])
                get_res.append(val)
        return get_res


    def get(self, key: int) -> int:
        # write code here
        if key in self.key_list:

            self.key_list.remove(key)
            self.key_list.insert(0,key)
            return self.capacity_data.get(key)
        else:
            return -1

    def set(self, key: int, value: int) :

        # write code here
#         print(len(self.capacity_data.keys()))
        if key not in self.key_list:
            if len(self.key_list)>=self.capacity:
                self.capacity_data.pop(self.key_list.pop())
                self.key_list.insert(0,key)
                self.capacity_data[key]=value
            else:
                self.key_list.insert(0,key)
                self.capacity_data[key]=value

        else:
            self.key_list.remove(key)
            self.key_list.insert(0,key)
            self.capacity_data[key]=value

请问这有什么bug

发表于 2022-06-08 11:47:00 回复(0)
Python 3
牛客537198052号头像 牛客537198052号
#
# lfu design
# @param operators int整型二维数组 ops
# @param k int整型 the k
# @return int整型一维数组

class Solution:
    def LFU(self, operators, k) :
        # write code here
        self.dic = dict()
        self.dic_freq = dict()
        self.list_freq = dict()
        self.min = 0
        self.k = k
        self.listreturn = []
        for operator in operators:
            if operator[0] == 1:
                self.set(operator[1], operator[2])
            elif operator[0] == 2:
                self.listreturn.append(self.get(operator[1]))
        return self.listreturn

    def set(self, key, value):
        if key in self.dic:
            freq = self.list_freq[key]
            self.dic[key] = value
            self.list_freq[key] = freq + 1
            self.dic_freq[freq].pop(self.dic_freq[freq].index(key))
            if freq+1 in self.dic_freq:
                self.dic_freq[freq+1].append(key)
            else:
                self.dic_freq[freq + 1] = []
                self.dic_freq[freq+1].append(key)
            if not self.dic_freq[freq]:
                self.min += 1
            
        else:
            if len(self.dic) < self.k:
                self.dic[key] = value
                self.min = 1
                self.list_freq[key] = 1
                if self.min in self.dic_freq:
                    self.dic_freq[self.min].append(key)
                else:
                    self.dic_freq[self.min] = []
                    self.dic_freq[self.min].append(key)
            else:
                rm = self.dic_freq[self.min].pop(0)
                self.list_freq.pop(rm)
                self.dic.pop(rm)
                self.dic[key] = value
                self.list_freq[key] = 1
                if len(self.dic_freq[self.min]) == 0:
                    self.dic_freq.pop(self.min)
                self.min = 1
                if self.min in self.dic_freq:
                    self.dic_freq[self.min].append(key)
                else:
                    self.dic_freq[self.min] = []
                    self.dic_freq[self.min].append(key)
                

    def get(self, key):
        if key in self.dic:
            freq = self.list_freq[key]
            self.list_freq[key] = freq + 1
            self.dic_freq[freq].pop(self.dic_freq[freq].index(key))
            if len(self.dic_freq[freq]) == 0:
                self.dic_freq.pop(freq)
            if freq+1 in self.dic_freq:
                self.dic_freq[freq+1].append(key)
            else:
                self.dic_freq[freq+1] = []
                self.dic_freq[freq+1].append(key)
            if self.min not in list(self.dic_freq.keys()):
                    self.min +=1
            value = self.dic[key]
            return value
        else:
            return -1
发表于 2022-04-10 09:21:45 回复(0)
Python 3
给个offer～头像 给个offer～

有序字典居然可以通过，只是尝试了一下。

def LFU(self , operators , k ):
        # write code here
        dic = collections.OrderedDict()
        ret = []
        for op in operators:
            if op[0] == 1:
                if len(dic) == k and op[1] not in dic:
                    keys = list(dic.keys())
                    min_key = keys[0]
                    for i in range(1,len(keys)):
                        if dic[keys[i]][1] < dic[min_key][1]:
                            min_key = keys[i]
                    dic.pop(min_key)
                if op[1] in dic:
                    dic[op[1]][0] = op[2]
                    dic[op[1]][1] += 1
                    value = dic[op[1]]
                    dic.pop(op[1])
                    dic[op[1]] = value
                else:
                    dic[op[1]] = [op[2],1]

            else:
                if op[1] not in dic:
                    ret.append(-1)
                else:
                    ret.append(dic[op[1]][0])
                    dic[op[1]][1] += 1
                    val = dic[op[1]]
                    dic.pop(op[1])
                    dic[op[1]] = val
        return ret
发表于 2021-08-10 17:29:21 回复(0)
提交观点

问题信息

模拟
难度：
9条回答 4104浏览

热门推荐

通过挑战的用户

查看代码

相关试题

设计LFU缓存结构

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号