题解 | #设计LFU缓存结构#TOP101

import java.util.*;


public class Solution {
    static class Node{
        int freq;
        int key;
        int val;
        public Node(int freq, int key, int val){
            this.freq = freq;
            this.key = key;
            this.val = val;
        }
    }
    //频率--链表的哈希表
    //相同频率的数据对应一个链表LinkedList，最先添加的在头部
    private Map<Integer, LinkedList<Node>> freq_mq = new HashMap<>();
    //key到节点Node的哈希表
    //记录每个key对应的节点，当存取值时取出Node的频率，根据频率取出对应的链表，移除当前Node，将Node添加到更高频次的链表中
    private Map<Integer, Node> mp = new HashMap<>();
    //记录缓存剩余容量
    private int size = 0;
    //记录最小频次
    private int min_freq = 0;
    /**
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LFU (int[][] operators, int k) {
        // write code here
        //operators
        this.size = k;
        //每个操作里面，第一个是取数据操作数
        int len = (int)Arrays.stream(operators).filter(x -> x[0] == 2).count();
        int[] res = new int[len];
        for(int i = 0, j = 0; i< operators.length; i++){
            if(operators[i][0] == 1){
                //set操作
                set(operators[i][1], operators[i][2]);
            }else{
                //get
                res[j++] = get(operators[i][1]);
            }
        }
        return res;
    }
    private void set(int key, int value){
        if(mp.containsKey(key)){
            //存在就 更新频率和节点值
            update(mp.get(key), key, value);
        }else{
            //哈希表中没有
            if(size == 0){
                //剩余容量没了
                int oldKey = freq_mq.get(min_freq).getLast().key;
                freq_mq.get(min_freq).removeLast();
                if(freq_mq.get(min_freq).isEmpty()){
                    freq_mq.remove(min_freq);
                }
                mp.remove(oldKey);
            }else{
                si***_freq = 1;
            if(!freq_mq.containsKey(1)){
                freq_mq.put(1, new LinkedList<Node>());
            }
            freq_mq.get(1).addFirst(new Node(1, key, value));
            mp.put(key, freq_mq.get(1).getFirst());
        }
    }
    private void update(Node node ,int key, int value){
        //找到频率
        int freq = node.freq;
        //原频率中删除该节点，因为频率变了
        freq_mq.get(freq).remove(node);
        //表中当前频率的数据没有了，直接清除，如果freq是最小频率，那么最小频率编程了min_freq+1
        if(freq_mq.get(freq).isEmpty()){
            freq_mq.remove(freq);
            if(min_freq == freq){
                min_freq ++;
            }
        }
        //插入频率 + 1的范围中
        if(!freq_mq.containsKey(freq + 1)){
            freq_mq.put(freq + 1 , new LinkedList<Node>());
        }
        //插入频率加1的链表里
        freq_mq.get(freq + 1).addFirst(new Node(1, key, value));
        mp.put(key, freq_mq.get(freq+1).getFirst());
    }
    private int get(int key){
        int res = -1;
        if(mp.containsKey(key)){
            Node node = mp.get(key);
            res = node.val;
            //更新频率
            update(node, key, res);
        }
        return res;
    }
}