get->o(1): map结构存key对应值 set->0(1): 双向链表存访问顺序。 1.访问到的已有节点:移除+尾插; 2.新节点:尾插,达到容量限制:头删。

import java.util.*;


public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {
        // write code here
        Lru lru = new Lru(k);
        int len = (int)Arrays.stream(operators).filter(x -> x[0] == 2).count();
        int[] res = new int[len];
        for(int i = 0, j = 0; i < operators.length; i++) {
            if(operators[i][0] == 1) {
                lru.set(operators[i][1], operators[i][2]);
            } else {
                res[j++] = lru.get(operators[i][1]);
            }
        }
        return res;
    }

    static class Lru {
        
        static class Node {
            public int key;
            public int val;
            public Node next;
            public Node pre;

            public Node(int key,int val, Node pre, Node next) {
                this.key = key;
                this.val = val;
                this.next = next;
                this.pre = pre;
            }
        }
        
        Map<Integer, Node> valMap = new HashMap();
        Node head;
        Node tail;
        int k;

        public Lru(int k) {
            this.k = k;
            head = new Node(-1,-1, null, null);
            tail = new Node(-99,-99, head, null);
            head.next = tail;
        }

        public void set(int key, int val) {
            Node node = getNode(key);
            if (node == null) {
                node = new Node(key,val, null, null);
                addLast(node);
                valMap.put(key, node);
                while (valMap.size() > k && head.next != tail && head != tail.pre) {
                    Node del = head.next;
                    delete(del);
                    valMap.remove(del.key);
                }
            } else {
                node.val = val;
            }
        }

        public int get(int key) {
            Node node = getNode(key);
            return node == null ? -1 : node.val;
        }

        public Node getNode(int key) {
            Node node = valMap.get(key);
            if (node != null && node.next != tail) {
                delete(node);
                addLast(node);
            }
            return node;
        }

        public void delete(Node node) {
            node.next.pre = node.pre;
            node.pre.next = node.next;
            node.next = null;
            node.pre = null;
        }

        public void addLast(Node node) {
            tail.pre.next = node;
            node.pre = tail.pre;
            tail.pre = node;
            node.next = tail;
        }
    }
    
}