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 tail;
int k;

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

public void set(int key, int val) {
Node node = getNode(key);
if (node == null) {
node = new Node(key,val, null, null);
valMap.put(key, node);
while (valMap.size() > k && head.next != tail && head != tail.pre) {
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);
}
return node;
}

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