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

NC93 设计LRU缓存结构

描述 设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 k ，并有如下两个功能

1. set(key, value)：将记录(key, value)插入该结构
2. get(key)：返回key对应的value值

提示: 1.某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的，然后都会刷新缓存。 2.当缓存的大小超过k时，移除最不经常使用的记录。 3.输入一个二维数组与k，二维数组每一维有2个或者3个数字，第1个数字为opt，第2，3个数字为key，value 若opt=1，接下来两个整数key, value，表示set(key, value) 若opt=2，接下来一个整数key，表示get(key)，若key未出现过或已被移除，则返回-1 对于每个opt=2，输出一个答案 4.为了方便区分缓存里key与value，下面说明的缓存里key用""号包裹

要求：set和get操作复杂度均为 O(1)

思路：定义两个方法，setKey和getKey，对应题目中的set和get操作。

setKey：当key在字典中时，将原字典中的item删除，然后再插入，这时，item在字典的尾部。当key不在字典中时，将{key，value}加入字典，这样保证字典尾部的数据是最新的，而字典首部的item是最旧的。setKey时，当长度超过给定长度时，将字典的第一个item删除。因为popitem删除的是字典尾部元素，pop需要给定key才能删除item，所以先获取第一个item的key。用list(dic)方法获取dic的key列表，key_list[0]就是要删除的item的key。

getKey：当key在字典中时，返回对应的value，且将对应的item提出到dic尾部（即删除原item，再加入该item）

setKey和getKey的复杂度为O(1),整个的复杂度为n，operators的数组长度

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# lru design
# @param operators int整型二维数组 the ops
# @param k int整型 the k
# @return int整型一维数组
#
class Solution:
    dic = {}
    def setKey(self,key,value,k):
        if key in self.dic:
            self.dic.pop(key)
        self.dic[key] = value
        if len(self.dic) > k:
            key_list = list(self.dic)
            self.dic.pop(key_list[0])
    def getKey(self,key):
        dic_get = self.dic
        if key in dic_get:
            value = self.dic[key]
            self.dic.pop(key)
            self.dic[key] = value
            return self.dic[key]
        else :
            return -1
    def LRU(self , operators: List[List[int]], k: int) -> List[int]:
        # write code here
        result = []
        for op in operators:
            if op[0] == 1:
                self.setKey(op[1],op[2],k)
            elif op[0] == 2:
                result.append(self.getKey(op[1]))
        return result