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

思路：
1.设计nod类来存储键值对。
2.设计lru类来模拟整个键值对队列。

import java.util.*;
public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {
        ArrayList<Integer> list=new ArrayList<>();
        Lru lru=new Lru(k);
        for(int[] operator:operators){
            //若是set
            if(operator[0]==1){
                nod n=new nod(operator[1],operator[2]);
                lru.set(n);
            }else{//若是get
                int i = lru.get(operator[1]);
                list.add(i);//返回值加入list
            }
        }
        int[] res=new int[list.size()];
        //list转数组
        for (int i = 0; i < list.size(); i++) {
            res[i]=list.get(i);
        }
        return res;
        // write code here
    }
}
//lru缓存结构类
class Lru{
    private int size;
    private int maxSize;
    LinkedList<nod> queue=new LinkedList<>();
    public Lru(int maxSize) {
        this.maxSize = maxSize;
    }
    public int getSize(){
        return queue.size();
    }
    //题目要求的set方法，即添加方法
    public void set(nod n){
        //先遍历队列看该键值是否存在
        for(nod nod:queue){
            //若存在，则直接把队列中的nod的value设置为添加点n的value
            if(nod.key==n.key){
                nod.value=n.value;
                return;
            }
        }
        //若不存在，且当前队列仍有空间，直接添加至队列末尾。
        if(getSize()<maxSize){
            queue.addLast(n);
        }else{//若不存在，则先把队列首的删除，再把nod添加至队列末尾。
            queue.removeFirst();
            queue.addLast(n);
        }
    }
    //题目要求的查找方法
    public int get(int index){
        int i=0;//记录nod的位置，便于删除的时候使用。
        //遍历队列
        for (nod nod : queue) {
            //查找到就，把原位置的nod删除，然后添加到队列末尾，即更新操作。
            if(nod.key==index){
                nod removeNod = queue.remove(i);
                queue.addLast(removeNod);
                return nod.value;
            }
            i++;
        }
        return -1;
    }
}
//键值对
class nod{
    int key;
    int value;
    public nod(int key, int value) {
        this.key = key;
        this.value = value;
    }
}