设计LRU缓存结构（python版）

这题文字有点多呀，实际上是让你设计数据结构：⾸先要接收⼀个 capacity 参数作为 缓存的最⼤容量，然后实现两个 API，⼀个是 put(key, val) ⽅法存⼊键值 对，另⼀个是 get(key) ⽅法获取 key 对应的 val，如果 key 不存在则返回 -1。要让 put 和 get ⽅法的时间复杂度为 O(1)，我们可以 总结出 cache 这个数据结构必要的条件：查找快，插⼊快，删除快，有顺序 之分。 因为显然 cache 必须有顺序之分，以区分最近使⽤的和久未使⽤的数据；⽽ 且我们要在 cache 中查找键是否已存在；如果容量满了要删除最后⼀个数 据；每次访问还要把数据插⼊到队头。

简单看下代码了解下吧

#
# lru design
# @param operators int整型二维数组 the ops
# @param k int整型 the k
# @return int整型一维数组
#
import collections
class Solution:
    def __init__(self, k):
        self.dic = collections.OrderedDict()
        self.capacity = k

    def get(self, key):
        if key not in self.dic: return -1
        val = self.dic.pop(key)
        self.dic[key] = val
        return val

    def set(self, key, value):
        if key in self.dic:
            self.dic.pop(key)
        else:
            if self.capacity > 0:
                self.capacity -= 1
            else:
                self.dic.popitem(last=False)
        self.dic[key] = value

s = input().strip()
idx = s.index("]],")
k = int(s[idx+3:])
ss = s[:idx]
aa = ss.strip("[[").split("],[")
s = Solution(k)
res = []
for r in aa:
    ss = list(map(int, r.strip().split(",")))
    if ss[0] == 1:
        s.set(ss[1], ss[2])
    elif ss[0] == 2:
        x = s.get(ss[1])
        res.append(x)
print(str(res).replace(" ", ""))

麻豆出品