力扣LFU缓存题解

题目链接：460. LFU 缓存 - 力扣（LeetCode） (leetcode-cn.com)

参考：Java 13ms 双100% 双向链表 多解法超全😂 - LFU 缓存 - 力扣（LeetCode） (leetcode-cn.com)，超详细图解+动图演示 460. LFU缓存 - LFU 缓存 - 力扣（LeetCode） (leetcode-cn.com)

思路：与LRU思路类似，Node结点中增加一个属性freq用于表示该项的使用次数，双向链表与LRU中的一致，LRUCache是Map+双向链表，而LFUCache是Map+Map<freq，双向链表>，因为LRU只需找出最久未使用的Node，而LFU需要找出使用次数最少（如果有多个使用次数最少的，则找出其中最久未使用的）

LRU对照学习

详情请参考另一篇力扣LRU缓存题解

class LRU {
    DoubleLinkedList list;
    HashMap<Integer, Node> map;
    int cap;

    public LRU(int cap) {
        list = new DoubleLinkedList();
        map = new HashMap<>();
        this.cap = cap;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        int value = map.get(key).value;
        put(key, value);
        return value;
    }

    private void put(int key, int value) {
        Node newNode = new Node(key, value);
        if (map.containsKey(key)) {
            list.delete(map.get(key));
        } else {
            if (map.size() > cap) {
                map.remove(list.delLast());
            }
        }
        list.addFirst(newNode);
        map.put(key, newNode);
    }
}

class DoubleLinkedList {
    Node head;
    Node tail;

    public DoubleLinkedList() {
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.next = tail;
        tail.prev = head;
    }

    public void addFirst(Node newNode) {
        newNode.next = head.next;
        newNode.prev = head;
        head.next.prev = newNode;
        head.next = newNode;
    }

    public int delete(Node node) {
        int res = node.value;
        node.prev.next = node.next;
        node.next.prev = node.prev;
        return res;
    }

    public int delLast() {
        if (head.next == tail) {
            return -1;
        }
        return delete(tail.prev);
    }
}

class Node {
    int key;
    int value;
    Node prev;
    Node next;

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

LFU

class LFUCache {
    // key为项的使用次数，value为相同使用次数的Node结点组成的双向链表
    HashMap<Integer, DoubleLinkedList> freqMap;
    // key为key，value为Node结点
    HashMap<Integer, Node> map;
    // 容量
    int cap;
    // 当前元素个数
    int size;
    // 所有元素中的最少使用次数
    int min;

    /**
     * 初始化
     * @param capacity
     */
    public LFUCache(int capacity) {
        // 新建map
        map = new HashMap<>();
        // 新建freqMap
        freqMap = new HashMap<>();
        // 容量
        this.cap = capacity;
        // 当前元素个数
        size = 0;
        // 最少使用次数为0
        min = 0;
    }

    /**
     * 通过key，获取相应的value的值
     * @param key
     * @return
     */
    public int get(int key) {
        // 如果map中不存在，则在freqMap也不存在，直接返回-1
        if (!map.containsKey(key)){
            return -1;
        }
        // 获取结点
        Node node = map.get(key);
        // 获取value
        int value = node.value;
        // 使该结点的使用次数增加1
        freqInc(node);
        // 返回value
        return value;
    }

    /**
     * 放入对应key、value的结点
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        // 如果LFU容量为0，直接返回
        if (cap==0){
            return;
        }
        // 从map中获取结点
        Node node = map.get(key);
        // 如果存在该结点
        if (node!=null){
            // 更改结点的value
            node.value=value;
            // 并增加其结点使用次数
            freqInc(node);
        }
        // 如果不存在该结点
        else {
            // 如果当前元素个数大于等于LFU容量
            if (size >= cap){
                // 获取使用次数最少的结点的双向链表
                DoubleLinkedList minList = freqMap.get(min);
                // 从map中移除最少最久未使用的结点
                map.remove(minList.tail.prev.key);
                // 从双向链表中删除该结点
                minList.delLast();
                // 当前元素个数减1
                size--;
            }
            // 新建node结点
            Node newNode = new Node(key, value);
            // 在map中放入结点
            map.put(key,newNode);
            // 获取使用次数为1的双向链表
            DoubleLinkedList list = freqMap.get(1);
            // 如果双向链表为空
            if (list==null){
                // 创建双向链表
                list = new DoubleLinkedList();
                // 将双向链表放入freqMap中
                freqMap.put(1,list);
            }
            // 将该结点加入到对应的双向链表中
            list.addFirst(newNode);
            // 当前元素个数加1
            size++;
            // 当前最少使用次数为1
            min=1;
        }
    }

    /**
     * 将传入结点的使用次数自增1，并将其移动到相应使用次数的双向链表
     * @param node
     */
    public void freqInc(Node node){
        // 获取当前结点的使用次数
        int freq = node.freq;
        // 获取对应使用次数的双向链表
        DoubleLinkedList list = freqMap.get(freq);
        // 在双向链表中删除该结点
        list.delete(node);
        // 如果删除的是使用次数最少的双向链表的最后一个结点
        if (min==freq && list.head.next==list.tail){
            min++;
        }
        // 结点使用次数自增1
        freq++;
        node.freq++;
        // 再次获取对应使用次数的双向链表
        list = freqMap.get(freq);
        // 如果双向链表为空
        if (list==null){
            // 创建双向链表
            list = new DoubleLinkedList();
            // 将双向链表放入freqMap中
            freqMap.put(freq,list);
        }
        // 将该结点加入到对应的双向链表中
        list.addFirst(node);
    }
}

/**
 * 自定义的双向链表
 */
class DoubleLinkedList {
    // 双向链表结构
    // next指针：head -> 第一个结点 -> 第二个结点 -> ... -> tail
    // prev指针：head <- 第一个结点 <- 第二个结点 <- ... <- tail
    
    // 双向链表的头结点
    Node head;
    // 双向链表的尾结点
    Node tail;

    /**
     * 新建双向链表
     */
    public DoubleLinkedList() {
        // 新建头结点
        head = new Node(-1, -1);
        // 新建尾结点
        tail = new Node(-1, -1);
        // 头结点的next指针指向尾结点
        head.next = tail;
        // 尾结点的prev指针指向头结点
        tail.prev = head;
    }

    /**
     * 将结点加入双向链表的头部
     */
    public void addFirst(Node newNode) {
        // 新结点的prev指针指向头结点
        newNode.prev = head;
        // 新结点的next指针指向头结点的下一个结点
        newNode.next = head.next;
        // 头结点的下一个结点的prev指针指向新结点
        head.next.prev = newNode;
        // 头结点的next指针指向新结点
        head.next = newNode;
    }

    /**
     * 在双向链表中删除对应的结点
     */
    public int delete(Node node) {
        // 拿到当前的结点的value
        int value = node.value;
        // 当前结点的下一个结点的prev指针指向当前结点的前一个结点
        node.next.prev = node.prev;
        // 当前结点的前一个结点的next指针指向当前结点的下一个结点
        node.prev.next = node.next;
        // 返回value
        return value;
    }

    /**
     * 删除尾结点的前一个结点
     */
    public int delLast() {
        // 如果双向链表为空，直接返回-1
        if (head.next == tail) {
            return -1;
        }
        // 删除最后一个结点，即尾结点的前一个结点
        return delete(tail.prev);
    }
}

/**
 * 自定义的node结点
 */
class Node {
    // key
    int key;
    // value
    int value;
    // prev指针
    Node prev;
    // next指针 
    Node next;
    // 结点使用次数
    int freq;

    /**
     * 创建node结点
     */
    public Node(int key, int value) {
        // key
        this.key = key;
        // value
        this.value = value;
        // 结点使用次数为1
        freq = 1;
    }
}