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

使用python进行解答，使到dist和[]的一些内置方法。

• cache_list:作为缓存
• tmp：记录最近使用的顺序
• result：记录操作结果（get操作）

代码：

#
# lru design
# @param operators int整型二维数组 the ops
# @param k int整型 the k
# @return int整型一维数组
#
class Solution:
    def LRU(self , operators , k ):
        cache_list = {}
        tmp = []
        result = []
        for operator in operators:
            print("==============================================================")
            # set操作
            if operator[0] == 1:
                print("当前操作是set：{}".format(operator))
                # 如果缓存已经满了，则更新
                if len(tmp) == k:
                    a=tmp.pop(0)
                    cache_list.pop(a)
                tmp.append(str(operator[1]))
                cache_list[str(operator[1])]=operator[2]
            else:
                print("当前操作是get：{}".format(operator))
#                 if cache_list.has_key(str(operator[1])):
                if str(operator[1]) in cache_list:
                    tmp.remove(str(operator[1]))
                    tmp.append(str(operator[1]))
                    result.append(cache_list[str(operator[1])])
                else:
                    result.append(-1)
            print("当前操作后的缓存为：{}".format(cache_list))
            print("缓存顺序为：{}".format(tmp))
            print("当前结果为：{}".format(result))
        return result

测试：

solution = Solution()
result= solution.LRU([[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3)
print(result)

输出：

==============================================================
当前操作是set：[1, 1, 1]
当前操作后的缓存为：{'1': 1}
缓存顺序为：['1']
当前结果为：[]
==============================================================
当前操作是set：[1, 2, 2]
当前操作后的缓存为：{'1': 1, '2': 2}
缓存顺序为：['1', '2']
当前结果为：[]
==============================================================
当前操作是set：[1, 3, 2]
当前操作后的缓存为：{'1': 1, '2': 2, '3': 2}
缓存顺序为：['1', '2', '3']
当前结果为：[]
==============================================================
当前操作是get：[2, 1]
当前操作后的缓存为：{'1': 1, '2': 2, '3': 2}
缓存顺序为：['2', '3', '1']
当前结果为：[1]
==============================================================
当前操作是set：[1, 4, 4]
当前操作后的缓存为：{'1': 1, '3': 2, '4': 4}
缓存顺序为：['3', '1', '4']
当前结果为：[1]
==============================================================
当前操作是get：[2, 2]
当前操作后的缓存为：{'1': 1, '3': 2, '4': 4}
缓存顺序为：['3', '1', '4']
当前结果为：[1, -1]
[1, -1]