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;
}
}
}