数据结构

1. 哈希
2. 双向链表

思路

1. 哈希结果作用
   • 用于以O(1)的复杂度获取目标节点
2. 双向链表作用
   • 用于记录完整LRU顺序，方便删除tail节点或head节点
   • 通过双向方式可以做到O(1)的操作节点

code

    private static final int[] EMPTY = new int[0];
    private static Pair head = null;
    private static Pair tail = null;
    private static int curSize = 0;

    class Pair {
        int value;
        int key;
        Pair previous = null;
        Pair next = null;
        public Pair(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public static int add(Pair pair) {
        if (head == null) {
            head = tail = pair;
            curSize++;
            return 1;
        }

        if (head == tail) {
            tail = pair;
            head.next = pair;
            tail.previous = head;
            curSize++;
            return 1;
        }

        pair.previous = tail;
        tail.next = pair;
        tail = pair;
        curSize++;
        return 1;
    }


    public static int delete(Pair pair) {
        if (head == null || pair == null) {
            return -1;
        }

        if (head == tail) {
            head = tail = null;
            curSize--;
            return 1;
        }

        Pair temp = null;
        if (head == pair) {
            temp = head.next;
            temp.previous = null;
            head.next = null;
            head = temp;
            curSize--;
            return 1;
        }

        if (tail == pair) {
            temp = tail.previous;
            tail.previous = null;
            temp.next = null;
            tail = temp;
            curSize--;
            return 1;
        }

        pair.next.previous = pair.previous;;
        pair.previous.next = pair.next;

        pair.next = null;
        pair.previous = null;
        curSize--;
        return 1;
    }




    public int[] LRU (int[][] operators, int k) {
        // write code here

        if (operators == null || operators.length == 0) return EMPTY;

        int len = 0;
        for (int i = 0; i < operators.length; i++) {
            int[] cur = operators[i];
            if (cur.length == 2) {
                len++;
            }
        }
        int[] result = new int[len];


        Map<Integer, Pair> map = new LinkedHashMap<Integer, Pair>();
        int resIndex = 0;
        for (int i = 0; i < operators.length; i++) {
            int[] cur = operators[i];

            if (cur.length == 2) {
                int key = cur[1];
                if (map.containsKey(key)) {
                    Pair pair = map.get(key);
                    delete(pair);
                    add(pair);
                    result[resIndex] = pair.value;
                } else {
                    result[resIndex] = -1;
                }
                resIndex++;
            } else {
                int key = cur[1];
                int value = cur[2];
                if (curSize < k) {
                    Pair pair = new Pair(key, value);
                    add(pair);
                    map.put(key, pair);
                } else {
                    int key1 = head.key;
                    map.remove(key1);
                    delete(head);
                    Pair pair = new Pair(key, value);
                    add(pair);
                    map.put(key, pair);
                }
            }
        }

        return result;
    }

其他优化

1. 复用节点降低内存
2. 部分位置安全性判断
3. 标志性参数可优化