1. 本题知识点

LRU

2. 题目描述

设计 LRU 缓存结构，该结构在构造时确定大小，假设大小为 K，并有如下两个功能

set(key, value)：将记录 (key, value) 插入该结构

get(key)：返回 key 对应的 value 值

[要求]

set 和 get 方法的时间复杂度为 O(1)

某个 key 的 set 或 get 操作一旦发生，认为这个 key 的记录成了最常使用的。

当缓存的大小超过 K 时，移除最不经常使用的记录，即 set 或 get 最久远的。

若 opt=1，接下来两个整数 x, y，表示 set(x, y)

若 opt=2，接下来一个整数 x，表示 get(x)，若 x 未出现过或已被移除，则返回 -1

对于每个操作 2，输出一个答案

输入：

[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3

输出：

[1,-1]

3. 解题思路

使用 Java 标准库 JDK 里的 LinkedHashMap

4. 代码

import java.util.*;public class Solution extends LinkedHashMap
   
    {
       class LRUCache extends LinkedHashMap
    
       {
           private int capacity;        public LRUCache(int capacity) {
               super(capacity, 0.75F,true);            this.capacity = capacity;        }        public int get(int key) {
               return super.getOrDefault(key,-1);        }        public void put(int key, int value) {
               super.put(key,value);        }        @Override        public boolean removeEldestEntry(Map.Entry
     
       eldest){
               return size() > capacity;        }    }    /**     * lru design     * @param operators int整型二维数组 the ops     * @param k int整型 the k     * @return int整型一维数组     */    public int[] LRU (int[][] operators, int k) {
           LRUCache lruCache = new LRUCache(k);        int[] res = new int[(int) Arrays.stream(operators).filter(x -> x[0] == 2).count()];        for(int i = 0, j = 0; i < operators.length; i++) {
               if(operators[i][0] == 1) {
                   lruCache.put(operators[i][1], operators[i][2]);            } else {
                   res[j++] = lruCache.get(operators[i][1]);            }        }        return res;    }}