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

static class Node{
    int key,value;
    Node pre,next;
    public Node(int key, int value){
        this.key=key;
        this.value=value;
    }
}
private HashMap<Integer,Node> lru = new HashMap<>();
private Node head = new Node(-1,-1);
private Node tail = new Node(-1,-1);
private int k;
public int[] LRU (int[][] operators, int k) {
    // write code here
    this.k = k;
    head.next=tail;
    tail.pre=head;
    int l = (int)Arrays.stream(operators).filter(x -> x[0] == 2 ).count();
    int j = 0;
    int[] result = new int[l];
    for(int i = 0 ; i < operators.length ; i++){
        if(operators[i][0]==1){
            set(operators[i][1],operators[i][2]);
            continue;
        }
        if(operators[i][0]==2){
            result[j] = get(operators[i][1]);
            j++;
        }
    }
    return result;
}

public void set(int key,int value){
    if(get(key)>-1){
        lru.get(key).value = value;
    }else{
        if(lru.size() >= k){
            tail.pre.pre.next = tail;
            Node p = tail.pre.pre;
            lru.remove(tail.pre.key);
            tail.pre = p;
        }
        Node n = new Node(key,value);
        n.pre = head;
        n.next = head.next;
        head.next.pre = n;
        head.next = n;
        lru.put(key,n);
    }
}

public int get(int key){
    if(lru.containsKey(key)){
        Node n = lru.get(key);
        n.pre.next = n.next;
        n.next.pre = n.pre;
        n.next = head.next;
        n.pre = head;
        head.next.pre = n;
        head.next = n;
        return n.value;
    }
    return -1;
}