题解 | #设计LRU缓存结构#明修栈道，暗度陈仓！

打个样

思路很简单，用List维护key的顺序，同时用Map记录键值对。
这样，表现上看是操作Map，实际上是操作List。
插入的时候，判断key是否存在于List：存在，则更新；反之，判断容量是否达到上限，无：则插入；有，则移除、插入。
查询的时候，判断key是否存在于List：存在，则返回对应value；反之，则返回-1.
完毕！

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) {
        // write code here
        LinkedList<Integer> res = new LinkedList<>();
        LinkedList<Integer> list = new LinkedList<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i=0;i<operators.length;i++){
            if (operators[i][0] == 1){
                // insert
                int key = operators[i][1];
                int value = operators[i][2];
                map.put(key,value);
                // if key in list
                if (list.contains(key)){
                    list.remove(list.indexOf(key));
                    list.addFirst(key);
                }else{
                    if (list.size()<k){
                        list.addFirst(key);
                    }else{
                        list.removeLast();
                        list.addFirst(key);
                    }
                }
            }else{
                // query
                int key = operators[i][1];
                int value = -1;
                if (list.contains(key)){
                    value = map.get(key);
                    list.remove(list.indexOf(key));
                    list.addFirst(key);
                }
                res.addLast(value);
            }
        }
        int[] nums = new int[res.size()];
        int i = 0;
        for (int r:res){
            nums[i++] = r;
        }
        return nums;
    }
}