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

双端队列+HashMap

看到很多使用链表维护的，其实可以直接使用Java的双端队列，本质上也是链表结构

public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    //使用双端队列维护缓存优先顺序，HashMap保存(key,value)值
    private Deque<Integer> deque = new LinkedList<>();
    private HashMap<Integer,Integer> map = new HashMap<>();
    private int k;
    public int[] LRU (int[][] operators, int k) {
        this.k = k;
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0; i < operators.length; i++){
            //插入操作
            if(operators[i][0] == 1){
                set(operators[i][1], operators[i][2]);
            }
            //查询操作
            else{
                list.add(get(operators[i][1]));
            }
        }
        int[] result = new int[list.size()];
        for(int i = 0; i < list.size(); i++)    result[i] = list.get(i);
        return result;
    }
    public void set(int key, int value){
        //如果缓存已满，移除队列首部元素
        if(map.size() == k){
            map.remove(deque.pollFirst());
        }
        //添加新元素
        map.put(key, value);
        deque.addLast(key);
    }
    public int get(int key){
        if(map.containsKey(key)){
            //队列中删除使用元素
            deque.remove(key);
            //在队列末端重新加入
            deque.addLast(key);
            return map.get(key);
        }else{
            return -1;
        }
    }
}