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

使用双向链表 HashMap实现O(1)

import java.util.*;


public class Solution {

    Map<Integer, Integer> map = new HashMap<>();
    Deque<Integer> list = new LinkedList<>();
    int k;

    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {
        // write code here

        ArrayList<Integer> res = new ArrayList<>();
        this.k = k;

        for (int[] op : operators) {
            if (op[0] == 1) {
                set(op[1], op[2]);
            } else {
                res.add(get(op[1]));
            }
        }

        return res.stream().mapToInt(Integer::valueOf).toArray();
    }

    private void set (int key, int value) {
        if (map.containsKey(key)) {
            list.remove(key);
        }
        list.offer(key);

        if (map.size() == k) {
            Integer rm = list.poll();
            map.remove(rm);
        }

        map.put(key, value);
    }

    public int get (int key) {
        if (map.containsKey(key)) {
            list.remove(key);
            list.offer(key);
            return map.get(key);
        }

        return -1;
    }

}