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

import java.util.*;


public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    HashMap<Integer, Node> map = new HashMap<>();
    int size = 0;
    int capacity = 0;
    Node head = null;
    Node tail = null;
    
    public int[] LRU (int[][] operators, int k) {
        int n = operators.length;
        List<Integer> list = new ArrayList<>();
        this.capacity = k;
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
        for(int i = 0; i<n; i++){
            if(operators[i][0] == 1){
                set(operators[i][1], operators[i][2]);
            }else{
                list.add(get(operators[i][1]));
            }
        }
        int[] ints = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ints[i] = list.get(i);
        }
        return ints;
    }
    
    public int get(int key){
        Node node = map.get(key);
        if(node == null) return -1;
        remove(node);
        moveToFirst(node);
        return node.val;
    }
    
    public void set(int key, int val){
        Node node = map.get(key);
        if(node == null){
            node = new Node(key, val);
            map.put(key, node);
            moveToFirst(node);
            this.size++;
            if(this.size > capacity){
                map.remove(tail.pre.key);
                remove(tail.pre);
                this.size--;
            }
        }else{
            node.val = val;
            remove(node);
            moveToFirst(node);
        }
    }
    
    public void remove(Node node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
    
    public void moveToFirst(Node node){
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
        node.pre = head;
    }
    
    static class Node{
        int val;
        int key;
        Node pre;
        Node next;
        public Node(){}
        public Node(int key, int val){
            this.key = key;
            this.val = val;
        }
    }
}