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

public class Solution {

Map<Integer,Node> cache = new HashMap<>();
public int capacity;
public int size;
public Node head;
public Node tail;

public int[] LRU (int[][] operators, int k){

    capacity = k;
    size = 0;
    head = new Node();
    tail = new Node();
    head.next = tail;
    tail.prev = head;

    List<Integer> result = new ArrayList<>();
    int len = operators.length;
    if(len == 0)
        return null;
    for(int i=0;i<len;++i){
        int[] temp = operators[i];
        if(temp[0] == 1){
            put(temp[1],temp[2]);
        }else{
            int val = get(temp[1]);
            result.add(val);
        }
    }

    int[] arr = result.stream().mapToInt(Integer::valueOf).toArray();
    return arr;
}

class Node{
    int key;
    int value;
    Node prev,next;
    public Node(){}

    public Node(int key,int value){
        this.key = key;
        this.value = value;
        this.prev = this.next = null;
    }
}

public int get(int key){

    Node node = cache.get(key);
    if(node == null){
        return -1;
    }else{
        moveToHead(node);
        return node.value;
    }
}

public void put(int key,int value){
    Node node = cache.get(key);
    if(node == null){
        Node newNode = new Node(key,value);
        addToHead(newNode);
        cache.put(key,newNode);
        ++size;
        if(size > capacity){
            Node node1 = deleteTail();
            cache.remove(node1.key);
            --size;
        }
    }else{
        node.value = value;
        moveToHead(node);
    }
}

public void addToHead(Node node){
    node.next = head.next;
    head.next.prev = node;
    node.prev = head;
    head.next = node;
}

public void deleteNode(Node node){
    node.next.prev = node.prev;
    node.prev.next = node.next;
    node.next = null;
    node.prev = null;
}

public void moveToHead(Node node){
    deleteNode(node);
    addToHead(node);
}

// 删除最后一个节点
public Node deleteTail(){
    Node node = tail.prev;
    deleteNode(node);
    return node;
}