JAVA原生支持

JAVA的linkedHashMap本身就支持LRU的。。。。 = =
面试你能这么写出来。 应该也算你过的。

 /**
     * lru design
     *
     * @param operators int整型二维数组 the ops
     * @param k         int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU(int[][] operators, int k) {
        LRUCache<Integer,Integer> lruCache = new LRUCache(k);
        List<Integer> result = new ArrayList<>();
        for (int[] operator : operators) {
            int opt = operator[0];
            if (opt == 1) {
                lruCache.put(operator[1], operator[2]);
            }
            if (opt == 2) {
                if (lruCache.containsKey(operator[1])) {
                    result.add(lruCache.get(operator[1]));
                } else {
                    result.add(-1);
                }
            }
        }
        return result.stream().mapToInt(i -> i).toArray();
    }

    class LRUCache<K, V> extends LinkedHashMap<K, V> {
        private final int CACHE_SIZE;

        /**
         * 传递进来最多能缓存多少数据
         *
         * @param cacheSize 缓存大小
         */
        public LRUCache(int cacheSize) {
            super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
            CACHE_SIZE = cacheSize;
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            // 当 map中的数据量大于指定的缓存个数的时候，就自动删除最老的数据。
            return size() > CACHE_SIZE;
        }
    }

队列 + HASH 表 ， ， 只超越18%的人。

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

class LRUCache {
    // 队列
    LinkedList<Integer> list = new LinkedList<>();
    // HASH表
    Map<Integer, Integer> hash = new HashMap<>();
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        int result = hash.getOrDefault(key, -1);
        if (result != -1) {
            //如果值不为空更新最近的KEY
            updateLessKey(key);
        }
        return result;
    }

    public void put(int key, int value) {
        hash.put(key, value);
        //如果容量超标
        if (hash.size() > capacity) {
            //删除最近的KEY
            hash.remove((Object) getLessKey());
        }
        //更新最近的KEY
        updateLessKey(key);
    }

    //获取最近的KEY ， 因为链表是队列的一种， 所以取对尾
    public int getLessKey() {
        int key = list.getLast();
        return key;
    }

    //  //更新最近的KEY
    public void updateLessKey(int key) {
        // 如果重复了， 先删除， 在添加
        if (list.contains(key)) {
            list.remove((Object) key);
        }
        list.addFirst(key);
        // 队列超标了也删除最后的。 
        if (list.size() > capacity) {
            list.removeLast();
        }
    }

}