双向链表+双哈希表

import java.util.*;


public class Solution {
    /**
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LFU (int[][] operators, int k) {
        // write code here
        int n = 0;
        for(int i = 0;i < operators.length;i++){
            if(operators[i][0] == 2)
                n ++;
        }
        int[] res = new int[n];

        LFU lfu = new LFU(k);
        int l = 0;
        for(int i = 0;i < operators.length;i++){
            if(operators[i][0] == 1){
                lfu.set(operators[i][1],operators[i][2]);
            }else if(operators[i][0] == 2){
                res[l++] = lfu.get(operators[i][1]);   
            }

        }

        return res;
    }
}

class LFU {

    private int capacity; // 缓存容量
    private int size; // 缓存中当前的节点数量
    private HashMap<Integer,Node> records;
    // 表示节点Node在哪个桶中
    private HashMap<Node,NodeList> heads;
    private NodeList headList; //整个结构中位于最左边的桶

    public LFU(int K){

        this.capacity = K;
        this.size = 0;
        this.records = new HashMap<>();
        this.heads = new HashMap<>();
        headList = null;
    }

    /**
     * 该函数的功能是：判断刚刚减少了一个节点的桶是否已经为空
     * 1、如果不为空，则什么也不做
     *
     * 2、如果为空，且removeNodeList是整个缓存结构中最左边的桶，则删除这个桶，同时让缓存结构
     * 中最左边的桶变为removeNodeList的下一个桶
     *
     * 3、如果为空，且removeNodeList不是整个缓存结构中最左边的桶，则删除这个桶，将removeNodeList前后的桶修改为
     * 直接双向连接
     * @param removeNodeList 表示刚刚减少了一个Node节点的桶
     * @return 返回值表示removeNodeList是否已经为空，空则返回true，否则返回false
     */
    private boolean modifyHeadList(NodeList removeNodeList){

        if (removeNodeList.isEmpty()){

            if (headList == removeNodeList){

                headList = removeNodeList.next;
                // 避免此时只有一个removeNodeList一个桶，而造成空指针异常
                if (headList != null){
                    headList.prev = null;
                }

            }else {

                removeNodeList.prev.next = removeNodeList.next;

                // 避免removeNodeList是最右边的桶，然后造成removeNodeList.next.prev产生空指针异常
                if (removeNodeList.next != null){
                    removeNodeList.next.prev = removeNodeList.prev;
                }
            }

            return true;
        }

        return false;
    }

    /**
     * 函数功能：当node节点的操作次数加1了，将这个节点从原来的桶中放入操作次数+1的桶中
     * 整个过程要保证桶之间仍然是双向链表，也要保证节点之间仍然是双向链表
     * @param node
     */
    private void move(Node node,NodeList oldNodeList){

        oldNodeList.deleteNode(node);

        // preList表示操作次数加1的后对应的那个桶的前一个桶
        // 如果oldNodeList删除node之后，空了，此时需要将oldNodeList删掉，那么次数加1后对应的那个桶的前一个桶就是oldNodeList.prev
        // 如果oldNodeList删除node之后，不空，那么oldNodeList依然是次数加1后对应的那个桶的前一个桶
        NodeList preList = modifyHeadList(oldNodeList) ? oldNodeList.prev : oldNodeList;

        NodeList nextList = oldNodeList.next;

        if (nextList == null){

            NodeList newList = new NodeList(node);
            if (preList != null){
                preList.next = newList;
            }
            newList.prev = preList;

            if (headList == null){
                headList = newList;
            }
            heads.put(node,newList);

        }else {

            if (nextList.head.times == node.times){

                nextList.addNodeToHead(node);
                heads.put(node,nextList);

            }else {

                NodeList newList = new NodeList(node);
                if (preList != null){
                    preList.next = newList;
                }

                newList.prev = preList;
                newList.next = nextList;
                nextList.prev = newList;

                if (headList == nextList){
                    headList = newList;
                }

                heads.put(node,newList);
            }
        }

    }

    public void set(int key,int value){

        if (records.containsKey(key)){

            Node node = records.get(key);
            node.value = value;
            node.times ++;
            NodeList curNodeList = heads.get(node);
            move(node,curNodeList);
        }else {

            if (size == capacity){
                Node node = headList.tail;
                headList.deleteNode(node);
                modifyHeadList(headList);
                records.remove(node.key);
                heads.remove(node);
                size --;
            }

            Node node = new Node(key, value, 1);
            if (headList == null){

                headList = new NodeList(node);
            }else {

                if (headList.head.times == node.times){

                    headList.addNodeToHead(node);
                }else {

                    NodeList newList = new NodeList(node);
                    newList.next = headList;
                    headList.prev = newList;
                    headList = newList;
                }
            }
            records.put(key,node);
            heads.put(node,headList);
            size ++;
        }
    }

    public int get(int key){

        if (!records.containsKey(key)){
            return -1;
        }

        Node node = records.get(key);
        node.times ++;
        NodeList curNodeList = heads.get(node);
        move(node,curNodeList);
        return node.value;
    }

    /**
     * 节点的数据结构
     */
    class Node{

        public int key;
        public int value;
        public int times; // 该节点发生set和get的次数总和

        public Node next;
        public Node prev;

        public Node(int key,int value,int times){

            this.key = key;
            this.value = value;
            this.times = times;
        }
    }

    /**
     * 桶的数据结构
     */
    class NodeList{

        public Node head; // 指向桶的头节点的指针
        public Node tail; // 指向桶的尾节点的指针
        public NodeList next;
        public NodeList prev;

        // 初始化
        public NodeList(Node node){

            head = node;
            tail = node;
        }

        /**
         * 将一个新的节点加入桶中，新的节点作为桶中新的头节点
         * @param newNode
         */
        public void addNodeToHead(Node newNode){
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }

        /**
         * 删除Node节点并保证node的上下文环境重新连接
         * @param node
         */
        public void deleteNode(Node node){

            if (head == tail){
                head = null;
                tail = null;
            }else {

                if (head == node){

                    head = node.next;
                    head.prev = null;
                }else if (node == tail){

                    tail = node.prev;
                    tail.next = null;

                }else {

                    node.next.prev = node.prev;
                    node.prev.next = node.next;
                }
            }
            node.next = null;
            node.prev = null;
        }

        public boolean isEmpty(){

            return head == null;
        }

    }
}