题解 | 设计LFU缓存结构

import java.util.*;


public class Solution {
    static  public int[] LFU (int[][] operators, int k) {

        maxCount = k;
        head.next = tail;
        tail.previous = head;


        int[] t = new int[operators.length];
        int index = 0;

        for (int[] operator : operators) {
            if (operator[0] == 1) {
                set(operator[1], operator[2]);
            }
            if (operator[0] == 2) {
                t[index++] = get(operator[1]);
            }
        }

        int[] reslt = new int[index];

        for (int i = 0; i < index; i++) {
            reslt[i] = t[i];
        }
        return reslt;
    }


    static class Node1 {
        int value;
        Node1 next;
        Node1 previous;

        Node1(int key, int value) {
            this.value = value;
            this.key = key;
            this.count = 1;
        }

        int key;
        int count;
    }

    //头节点
    static Node1 head = new Node1(Integer.MAX_VALUE, Integer.MAX_VALUE);
    //尾节点
    static Node1 tail = new Node1(Integer.MIN_VALUE, Integer.MIN_VALUE);

    //当前值
    static int count;

    static int maxCount;

    static Map<Integer, Node1> map = new HashMap<>();



    static public int get(int key) {
        Node1 node3 = map.get(key);
        if (node3 == null) {
            //System.out.print("-1 ");
            return -1;
        } else {
            //数量+1
            node3.count = node3.count + 1;
            //从当前节点往前找，找到第一个大于当前数量的节点,记为目标节点
            Node1 currentNode = node3.previous;

            while (currentNode != head && currentNode.count <= node3.count) {
                currentNode = currentNode.previous;
            }

            //断开当前的连接
            //当前节点的前置节点的下一个设置成当前节点的下一个
            // 假设当前节点是2，原来的前置链表(next)是 1->2->3，后置链表(previous)是 3->2->1
            // 则修改后前置链表(next)是 1->3
            node3.previous.next = node3.next;
            // 假设当前节点是2，原来的前置链表(next)是 1->2->3，后置链表(previous)是 3->2->1
            // 则修改后置链表(previous)是 3->1
            node3.next.previous = node3.previous;

            //当前节点指向目标节点后的第一个节点
            node3.next = currentNode.next;

            //目标节点后的第一个节点的上一个指向当前节点
            currentNode.next.previous = node3;

            //目标节点指向当前节点(因为当前节点变成第一个节点了)
            currentNode.next = node3;

            //当前节点的上一级指向目标节点
            node3.previous = currentNode;

            //System.out.print(node3.value + " ");
            return node3.value;
        }

    }

    static public void set(int key, int value) {
        Node1 node3 = map.get(key);
        //如果包含，需要移动位置
        if (map.get(key) != null) {

            node3.value = value;
            map.put(key, node3);

            //数量+1
            node3.count = node3.count + 1;
            //从当前节点往前找，找到第一个大于当前数量的节点,记为目标节点
            Node1 currentNode = node3.previous;

            while (currentNode != head && currentNode.count <= node3.count) {
                currentNode = currentNode.previous;
            }
            //断开当前的连接
            //当前节点的前置节点的下一个设置成当前节点的下一个
            // 假设当前节点是2，原来的前置链表(next)是 1->2->3，后置链表(previous)是 3->2->1
            // 则修改后前置链表(next)是 1->3
            node3.previous.next = node3.next;
            // 假设当前节点是2，原来的前置链表(next)是 1->2->3，后置链表(previous)是 3->2->1
            // 则修改后置链表(previous)是 3->1
            node3.next.previous = node3.previous;

            //当前节点指向目标节点后的第一个节点
            node3.next = currentNode.next;

            //目标节点后的第一个节点的上一个指向当前节点
            currentNode.next.previous = node3;

            //目标节点指向当前节点(因为当前节点变成第一个节点了)
            currentNode.next = node3;

            //当前节点的上一级指向目标节点
            node3.previous = currentNode;

        } else {
            count++;
            Node1 node = new Node1(key, value);
            map.put(key, node);

            //从当前节点往前找，找到第一个大于当前数量的节点,记为目标节点
            Node1 currentNode = tail.previous;
            while (currentNode != head && currentNode.count <= 1) {
                currentNode = currentNode.previous;
            }
            //当前节点指向目标节点后的第一个节点
            node.next = currentNode.next;
            //目标节点后的第一个节点的上一个指向当前节点
            currentNode.next.previous = node;

            //目标节点指向当前节点(因为当前节点变成第一个节点了)
            currentNode.next = node;
            //当前节点的上一级指向目标节点
            node.previous = currentNode;

            //数量已达上限，删除一个
            if (count > maxCount) {
                count--;
                Node1 node1 = tail.previous;

                if (node1 == node) {
                    node1 = node1.previous;
                }
                Node1 node2 = node1.previous;
                if (node2 != null) {
                    tail.previous = node2;
                    node2.next = tail;
                }
                map.remove(node1.key);
                //最后一个如果大于1，则需要把它删除后
            }
        }

    }
}

这里采用双向链表+Map的方式来完成。

首先定义一个头节点和尾节点来确保可以找到根节点。

再定义一个节点值

static class Node {
        //值
        int value;
        //下一个指针
        Node next;
        //上一个指针
        Node previous;

        Node(int key, int value) {
            this.value = value;
            this.key = key;
            this.count = 1;
        }

        //key
        int key;
        //访问的数量
        int count;
    }

初始化的时候，先把头节点next指向尾节点。尾节点的previous指向头节点。

当插入一个数据的时候，初始化数量为1.把它放入map中。

从尾节点开始，随着previous指针往前找，找到第一个数量大于1的。

当前节点就排在它的后面即可。

这里有一个细节，如果数量超过了，当前节点又是在最后，那么就会把它淘汰掉，这是错的，应该淘汰它前面这一个。

所以淘汰的时候应该判断一下当前插入的节点是否是最后一个，如果是，就往前走一步。

更新值和查找值的时候，原理差不多，不同点在于，不是从最后开始找，可以直接从map里获取值。

步骤为

（1）先把数量+1

（2）随着previous指针往前找，找到第一个数量大于当前节点数量的节点，记为节点A。

（3）断开当前的连接。

（4）在A的后面插入当前节点。