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

算法思路

题目要求设计一个LRU（Least Recent Used）缓存结构，即优先淘汰最久没有使用到的数据。最常规做法就是使用一个List将缓存索引保存起来：当缓存中每插入一条数据，就往List头插入该数据索引；而每次缓存被命中时，则将该数据索引挪到List头部；此外再用一个Map来保存缓存索引跟缓存值得关系；在缓存淘汰的时候，同时刷新List跟Map即可；

算法实现

    public int[] LRU(int[][] operators, int k) {
        List<Integer> result = new ArrayList<>();
        ArrayList<Integer> lruKey = new ArrayList<>();
        Map<Integer, Integer> lruMap = new HashMap<>();
        for (int[] operator : operators) {
            int opt = operator[0];
            if (opt == 1) {
                // 缓存淘汰：移除最不常用数据
                if (lruKey.size() == k) {
                    Integer oldKey = lruKey.remove(lruKey.size() - 1);
                    lruMap.remove(oldKey);
                }
                // 插入一条缓存记录
                lruKey.add(0, operator[1]);
                lruMap.put(operator[1], operator[2]);
            } else if (opt == 2) {
                Integer key = operator[1];
                // 缓存命中：将被命中数据移到头部
                if (lruKey.contains(key)) {
                    result.add(lruMap.get(key));
                    lruKey.remove(key);
                    lruKey.add(0, key);
                } else {
                    result.add(-1);
                }
            }
        }

        return result.stream().mapToInt(Integer::intValue).toArray();
    }