文章目录的主题记述解题思路代码如下
主题说明牛客链接
设计LRU (最近使用的)缓存结构。 该结构在构建时确定大小(假设大小为k )，具有以下两个功能
set(key，value ) :将记录(key，value )插入此结构set(key ) )返回与key对应的value值提示：
1 .一个key的设置或获取操作发生时，该key的记录被认为是最常用的，缓存会被刷新。
2 .缓存大小超过k时，删除最不常用的记录。
3.输入二维数组和k。 二维数组每个一维有两个或三个数字，第一个数字是opt，第二个，第三个数字是key，value
当opt=1时，以下两个整数key、value表示set(key、value )
如果opt=2，则以下整数key表示get(key )，如果key不出现或删除，则返回-1
每opt=2输出一个回答
4 .为了便于区分缓存中的key和value，以下描述的缓存中的key被“”包裹
高级：你能用o(1)的时间复杂度完成set和get的操作吗
示例1
[ 1，1，1 ]、[ 1，2，2 ]、[ 2，1 ]、[ 1，3，3 ]、[ 2，2 ]、[ 1，4，4 ]、[ 2，1，1 ]、[ 2，3 ]、[ 2，3 ]
复制返回值： [1，-1，- 1，3，4 ]
示例2
输入： [1，1，1 ]、[ 1，2，2 ]、[ 1，3，2 ]、[ 2，1 ]、[ 1，4，4 ]、[ 2，2 ]，3返回值： [ 1，-1]副本
说明： [ 1，1，1 ]，前一个表示opt=1，要设置(1，1 )，请将) 1，1插入缓存。 缓存为{“1”=1}
[ 1，2，2 ]，前1表示opt=1，要进行set (2，2 )，即) 2，2 )插入缓存。 高速缓存为{“1”=1，“2”=2}
[ 1，3，2 ]，前1表示opt=1，要进行set (3，2 )，也就是说，在之前) 3，2中插入缓存。 高速缓存是{“1”=1、“2”=2、“3”=2}
[ 2，1 ]，前2表示opt=2，求出get(1)，返回为)1)。 这是因为，通过get )1)的操作，缓存被更新，缓存为{“2”=2、“3”=2、“1”=1}
[ 1，4，4 ]，前1表示opt=1，要进行set (4，4 )，即插入) 4，4 )缓存，但缓存已经达到最大容量3，使用频率最低)“2”=2)
[ 2，2 ]，前2表示opt=2，要进行get(2)，就找不到。 返回值为[1，-1]
解决问题首先要实现这个set和get方法。 和Map一样，利用set设定键-值对。 key:value，key不能重复。 之后输入现有的key将复盖原始数据。 在问题中，k表示该缓存大小，如果数据超过此值，则丢弃即使经过一段时间也不使用的数据。 也就是说，在最前端不更新的数据被废弃的本人使用两个队列来实现LRU缓存结构。 队列中存储了链表，0和1分别表示使用set添加的key和value，使用映射进行计数。 记录输出的key在输入时发生了多少次更改，以最新的一次为基准，其他的用key从队列中取出，更新后的新数据通过其他队列最后入队()
代码如下所示： import java.util.*； public class solution {/* * * lrudesign * @ paramoperatorsint整数型二维数组the ops * @param k int整数型the k * @return int整数型一维数组*/public int intk (//writecodeherequeuelistintegerqueue1=新链接列表)； //就绪队列queuelistintegerqueue2=新链接列表(； //次队列ListInteger r=new ArrayList (； //记录输出信息MapInteger，Integer map=new HashMap (； //记录输出的key被修改了多少次的for(intI=0； i operators.length； I ) {列表integer list1=new ArrayList (； if (操作器[ I ] [0]==1) {/opt=1list1. add (操作器[ I ] [1] )； if (！ map.contains key (operators[I][1] ) (map.put ) operators [ I ] [1]，1 )； }else{map.put(operators[I][1]，map.get ) operators[I][1] )1)； }list1.add(operators[I][2]； if(queue1.size(==k ) ) { queue1.poll )； }queue1.offer(list1)； }else{//opt=2 boolean flg=false； while (！ queue1.isEmpty () { ListInteger ret=queue1.peek； inttmp=ret.get(0； if(tmp！=operators [ I ] [1] (queue2. offer queue1. poll ) )； }else{intcount=map.get(tmp )； //更新了几次，最后flg=true； while (！ queue1.isEmpty () if ) tmp==queue1.peek ).get )0) ) if ) count==1) ) r.add ) queue1.peek ).get )。 //将输出的值保存在r ret=queue1.poll (中的map.put(tmp，1 )； }else{ count--； queue1.poll (； //舍弃输入}}else{queue2.offer(queue1.poll ) )； }queue2.offer(ret )； }if(flg==false ) r.add(-1 )； (//永远排队queue1while (！ queue2.isEmpty () ) queue1. offer (queue2. poll ) )； }}int[]arr=newint[r.size(]； for(intI=0； i r.size (； I ) {arr[I]=r.get(I )； }返回arr； }