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

设计LRU缓存结构
哈希表+顺序链表(理解为散列表+队列)
其原理在于：
哈希表用于存储数据；
队列用于记录顺序；

public int[] LRU (int[][] operators, int k) {
        // write code here
        //用于记录最新访问的队列
        ArrayList<Integer> table=new ArrayList<>();
        //用于存储数据的哈希表【使用String作为key的类型避免了重写比较方法】
        HashMap<String,Integer> map=new HashMap<>();
        //用于记录输出的集合
        ArrayList<Integer> r=new ArrayList<>();
        //遍历输入集
        for(int[] m:operators){
            //以首个数据为关键字划分策略
            switch(m[0]){
                //为1执行插入
                case 1:
                   //如果表还未满
                   if(table.size()<k){
                       //插入的key值
                       int key=m[1];
                       //插入的value值
                       int value=m[2];
                      //检查是否已经包含该key
                      if(map.containsKey(key)){
                          //包含的情况移除该key在队列中的位置【因为传入int型数据会调用index的方法这里使用包装类】
                          table.remove(new Integer(key));
                          //将key加入队列末尾
                          table.add(key);
                          //更新值
                          map.put(key+"",value);
                      }else{
                          //如果不包含该key，向队列末尾添加该key
                          table.add(key);
                          //添加值
                          map.put(key+"",value);
                      }

                   } else{
                       //如果表已满
                       int key=m[1];
                       int value=m[2];
                       //获取队列中，最前面的key值
                       int oldKey=table.get(0);
                       //从队列中移出该key
                       table.remove(new Integer(oldKey));
                       //添加新key
                       table.add(key);
                       //在表中移出旧的值
                       map.remove(oldKey+"");
                       //添加新值
                       map.put(key+"",value);
                   }
                    break;
                //为2执行查询
                case 2:

                    int gkey=m[1];
                    if(map.get(gkey+"")==null){
                        //为空则将输出集中加入-1
                        r.add(-1);
                    }else{
                        //不为空加入查询结果
                        r.add(map.get(gkey+""));
                        //移出队列中该key的位置，并将其加在队列末尾
                        table.remove(new Integer(gkey));
                        table.add(gkey);
                    }

            }
        }
        //将结构转换为函数标准输出并返回。
        final int size=r.size();
        int[] re=new int[size];
        for(int i=0;i<r.size();i++){
            re[i]=r.get(i);
        }
        return re;
    }