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

'''
解题思路：
1、设计key, value, res三个list
2、插入操作：分key中已有和没有2种情况，已有时删除原值。在0位插入新key和value,长度大于k截断
3、读取操作：分key中已有和没有2种情况，没有时返回-1，有时返回value值。删除原位置，在0位插入key和value
'''
#
# lru design
# @param operators int整型二维数组 the ops
# @param k int整型 the k
# @return int整型一维数组
#
class Solution:
    def LRU(self , operators , k ):
        # write code here
        key = []
        value = []
        res = []
        for op in operators:
            if op[0]==1:
                if op[1] in key:
                    index = key.index(op[1])   
                    key.pop(index)
                    value.pop(index)
                key.insert(0,op[1])
                value.insert(0,op[2])
                if len(key)>k:
                    key = key[:k]
                    value = value[:k]
            if op[0]==2:
                if op[1] not in key:
                    res.append(-1)
                else:
                    index = key.index(op[1])
                    t = value[index]
                    res.append(t)
                    key.pop(index)
                    value.pop(index)
                    key.insert(0,op[1])
                    value.insert(0,t)
        #print(res)
        return res

operators =[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]]
k = 3
Solution().LRU(operators,k)