吐槽下,这个题太麻烦了面试可能不会出,而且网上的做法好多不是O(1)的
/*
1. 需求:
1.1 功能性需求: 记录访问频率, 在空间不足时回收频率较低的空间, 频率相同回收先进入cache的值
1.2 非功能需求: 读写O(1)


2. 设计:
2.1 因为读写都是串行的,所以记录2类指针:
2.1.1 一个是和LRU一样把所有Node串起来,使插入和删除都为O(1), 高频在表头,低频在表尾, 先进入数据靠近表头, 后进入的靠近表位
2.1.2 另外再维护两个个HashMap,记录频率对应的Node最后位置和开始位置
2.2 HashMap 存数据

3. 实现
3.1  调整Node 位置:
3.1.1 freq++, 获取key当前状况, 找到下一个频率的表尾插入

3.2 回收空间:
3.2.1 通过 tail.prev 回收时找到最低频率的表头删除


4. testcase:
容量: 0 , 非0不超出, 非0超出, 交错
回收: 频率不同, 频率相同
更新频率: 多次get更新, 多次put不同的更新, 多次put相同的更新

*/


class LFUCache {

    public class Node{
        int key, value, freq;
        Node prev, next;

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

    int capacity, size;
    Node head, tail;
    Map<Integer, Node> data, start, end;


    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        data = new HashMap<>();
        start = new HashMap<>();
        end = new HashMap<>();
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = data.get(key);
        if (node == null) return -1;
        adjustIndex(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (this.capacity == 0) return;

        Node node = data.get(key);

        if (node == null) {
            garbageCollect();
            node = new Node(key, value);
            data.put(key, node);
            appendIndex(node, tail.prev);
            this.size++;
        } else {
            node.value = value;
        }
        adjustIndex(node);
    }

    private void removeByList(Node node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void appendByList(Node node, Node ptr){
        node.prev = ptr;
        node.next = ptr.next;
        ptr.next.prev = node;
        ptr.next = node;
    }

    private Node removeByMap(Node node){

        Node thisFreqHead = start.get(node.freq);
        Node thisFreqTail = end.get(node.freq);
        if (thisFreqTail == node){
            if (node.prev.freq == node.freq){
                end.put(node.freq, node.prev);
            } else {
                end.remove(node.freq);
            }
        }

        if (thisFreqHead == node) {
            if (node.next.freq == node.freq){
                start.put(node.freq, node.next);
            } else {
                start.remove(node.freq);
            }
        }

        return thisFreqHead;
    }

    private Node appendByMap(Node node){
        Node newFreqHead = start.get(node.freq);
        Node newFreqTail = end.get(node.freq);

        if (newFreqTail == null) {    
            start.put(node.freq, node);
        }
        if (newFreqHead == null){
            start.put(node.freq, node);
        }
        end.put(node.freq, node);

        return newFreqHead;
    }

    private Node removeIndex(Node node){
        removeByList(node);
        return removeByMap(node);
    }

    private Node appendIndex(Node node, Node ptr){
        appendByList(node, ptr);
        return appendByMap(node);
    }

    private void adjustIndex(Node node){
        Node highFreqTail = end.get(node.freq + 1);
        Node thisFreqHead = removeIndex(node);
        Node ptr = highFreqTail == null ? thisFreqHead.prev: highFreqTail;
        node.freq++;
        appendIndex(node, ptr);
    }

    private void garbageCollect(){
        while (this.size >= this.capacity){
            Node node = start.get(this.tail.prev.freq);
            removeIndex(node);
            data.remove(node.key);
            this.size--;
        }
    }
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */