题解 | #设计LFU缓存结构# TreeMap保存频率

1. 合适的数据结构
2. 清晰的思路，在往map add元素前，就判断map的size

import java.util.*;
class Node {
    int key;
    int value;
    int fre;
    Node(int key, int value, int fre) {
        this.key = key;
        this.value = value;
        this.fre = fre;
    }
}
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    // 实现get
    HashMap<Integer, Node> map = new HashMap<>();
    // key 为频率，value为 node集合
    // 上次调用发生最早的key被删除 需要用list
    TreeMap<Integer, List<Node>> tree = new TreeMap<>();
    public void addFre(Node node, int fre) {
        List<Node> list = tree.getOrDefault(fre, new ArrayList<>());
        list.add(node);
        tree.put(fre, list);
    }
    public void  deleteFre(Node node, int fre) {
        List<Node> list  = tree.get(fre);
        if (list != null) {
            list.remove(node);
            if( list.size()==0) {
                tree.remove(fre);
            }
        }
    }
    public void updateFre(Node node) {
        // 从之前频率list移除
        deleteFre(node, node.fre);
        // 因为访问了 fre+1
        node.fre += 1;
        addFre(node, node.fre);
    }
    public int[] LFU (int[][] operators, int k) {
        int len = operators.length;
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            int key = operators[i][1];
            Node node = map.get(key);
            if (operators[i][0] == 1) {
                // set
                int value = operators[i][2];
                if (node == null) {
                    node = new Node(key, value, 0);
                    // map容量会变大，提前删除
                    if (map.size() == k ) {
                        Map.Entry<Integer, List<Node>> entry = tree.firstEntry();
                        List<Node> list = entry.getValue();
                        Node n = list.remove(0);
                        map.remove(n.key);
                    }
                    map.put(key, node);

                } else {
                    node.value = value;
                }
            } else {
                // get
                if (node == null) {
                    res.add(-1);
                    continue ;
                }
                res.add(node.value);
            }
            updateFre(node);
        }
        int arr[] = new int[res.size()];
        int i = 0;
        for (int value : res) {
            arr[i++] = value;
        }
        return arr;
    }
    //input [[1,1,1],[1,2,2],[1,3,3],[1,4,4],[2,4],[2,3],[2,2],[2,1],[1,5,5],[2,4]],4
    //output [4,3,2,1,-1]
}