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

/**
     * LinkedHashMap本身就是一个LRU缓存，其数据结构是双链表+hashMap
     * put操作：把数据放到链表末尾，当超过指定大小后，会删除链表首节点
     * get操作：把数据放到链表末尾。
     * @param <K>
     * @param <V>
     */
    static class MyLinkedHashMap<K, V> extends LinkedHashMap<K, V>{
        private Integer maxNumber;

        public MyLinkedHashMap(int initialCapacity, float loadFactor) {
            super(initialCapacity, loadFactor, true);
        }

        public Integer getMaxNumber() {
            return maxNumber;
        }

        public void setMaxNumber(Integer maxNumber) {
            this.maxNumber = maxNumber;
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > getMaxNumber(); // 超过指定的大小会删除head节点
        }
    }

 public static int[] LRU (int[][] operators, int k) {
        int[] lruTmp = new int[operators.length];
        MyLinkedHashMap<Integer, Integer> map = new MyLinkedHashMap<>(16, 0.75f);
        map.setMaxNumber(k);
        int i=0;
        int j=0;
        for (int[] op: operators){
            if (op.length==3){
                map.put(op[1], op[2]);
            }else {
                lruTmp[i++]=map.getOrDefault(op[1], -1);
                j++;
            }
        }
        int[] lru = new int[j];
        for (int m=0;m<lruTmp.length; m++){
            if (lruTmp[m]!=0){
                lru[m]=lruTmp[m];
            }
        }
        return lru;
    }