农场主有一个牛棚，牛棚里有一些牛，每头牛都有一个整数编号。农场主希望设计一个缓存系统，用于快速查找牛的编号。缓存系统需要满足 LRU（最近最少使用）缓存约束。请实现一个牛棚缓存类： BarnCache 类： BarnCache(int capacity)：以正整数作为容量 capacity 初始化牛棚缓存。 vector operate(vector& operations)：对缓存进行一系列操作，每个操作由一个整数表示。操作的含义如下： 1：put。后面跟着两个整数 key 和 value，表示将 key-value 插入缓存。 2：get。后面跟着一个整数 key，表示获取 key 对应的值。如果 key 存在，则返回对应的值，否则返回 -1。 函数 operate 必须以 O(1) 的平均时间复杂度运行。
示例1

输入

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

输出

[1,2,-1,3,4]
示例2

输入

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

输出

[-1,-1,-1,-1,4]

备注:
1 0 0 最多调用 2 * 10^5 次 get 和 put
加载中...