题解 | #设计LFU缓存结构，双hash表+链表#

import java.util.*;


class Node {//节点（数据单元）
    int key ;
    int val ;
    int count ;//节点访问的次数
    Node(int key , int val) {
        this.key = key ;
        this.val = val ;
    }
}
class LFU {//缓存结构
    //根据key查询Node
    HashMap<Integer , Node> dic ;
    /*根据访问次数count查询List（list里面存储所有访问次数为count的节点，并且约靠近链尾的节点约久未访问）*/
    HashMap<Integer , LinkedList<Node>> tim ;
    int minTim ;//被访问最少的节点的 访问次数
    int maxSize ;//LFU缓存的容量
    int size ;//当前使用的容量
    LFU(int capcity) {
        this.dic = new HashMap<>() ;
        this.tim = new HashMap<>() ;
        this.minTim = 0 ;  
        this.maxSize = capcity ;
        this.size = 0 ;
    }
    //set(key,value)
    public void set(int key , int val) {
        if(dic.containsKey(key)) {//如果缓存中存在key
            Node find = dic.get(key) ;
            find.val = val ;//置换key所对应的value
            flush(find) ;//刷新一下访问记录，即让当前的访问次数加一，并且从原来的链表移动到新的链表
        } else {//如果缓存中不存在key
            Node newNode = new Node(key , val) ;//新建节点
            newNode.count = 1 ;//第一次访问
            if(this.size == this.maxSize) {//如果缓存满了
                removeByLFU() ;//置换        
            } else {//缓存未满，size加一
                this.size ++ ;
            }
            dic.put(key , newNode) ;//存数据
            if(tim.containsKey(1)) {//如果已经存在次数为1的链表
                tim.get(1).addFirst(newNode) ;//直接添加，在链头哦
            } else {//如果不存在次数为1的链表
                LinkedList<Node> newList = new LinkedList<>() ;//新建一个链表
                newList.add(newNode) ;//添加
                this.minTim = 1 ;//刷新最小访问次数
                tim.put(1 , newList) ;//将该链表以key为1,存入tim
            }
        }
    }
    //get(key)
    public int get(int key) {
        if(!dic.containsKey(key)) return -1 ;//不存在直接返回-1
        Node find = dic.get(key) ;//得到对应的节点
        flush(find) ;//刷新节点的访问记录
        return find.val ;
    }
    //刷新节点的访问记录
    public void flush(Node find) {
        LinkedList<Node> oldBelongsList = tim.get(find.count) ;//获取节点原来所在的链表
        oldBelongsList.remove(find) ;//从原来的链表中移除
        if(oldBelongsList.size() == 0) {//如果原来的链表已经没有数据了
            if(find.count == this.minTim) {//并且 当前节点就是最少访问节点，那么要更新最少访问节点的访问次数
                this.minTim ++ ;    
            }
            tim.remove(find.count) ;//把空链表移除
        }
        find.count ++ ;//当前节点的访问次数+1
        if(tim.containsKey(find.count)) {//如果新的访问次数岁对应的链表已经存在
            tim.get(find.count).addFirst(find) ;//则直接在新的链表中加入当前节点
        } else {//如果新的访问次数岁对应的链表不存在
            LinkedList<Node> newBelongsList = new LinkedList<>() ;//创建链表
            newBelongsList.add(find) ;//添加节点
            tim.put(find.count , newBelongsList) ;//将新的链表加入到tim中
        }
    }
    //（淘汰访问次数最少的节点，次数一样则淘汰最久未访问的节点）
    public void removeByLFU() {
        LinkedList<Node> minTimList = tim.get(this.minTim) ;//获取最少访问次数所对应的链表
        Node target = minTimList.get(minTimList.size()-1) ;//获取这个访问次数的"众多"节点中的最久未访问哪一个节点（即，链表尾部的那个节点）
        minTimList.remove(target) ;//删除那个节点
        if(minTimList.size() == 0) {//如果这个链表已经空了，则将其从tim中移除掉
            tim.remove(this.minTim) ;
        }
        dic.remove(target.key) ;//将节点从dic中移除
        //注意：这个方法中并没有更新size和minTim,因为客户在调用本方法后，必定会再增加一个节点
        //然后将minTim设置为1,(所以在本方法更新size和minTim多余，至少在这种实现的方式下是的，嘿嘿，才疏学浅，见谅！！)
    }
}
public class Solution {
    /**
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LFU (int[][] operators, int k) {
        int getCount = (int)(Arrays.stream(operators).filter(a->a[0] == 2).count()) ;
        int res[] = new int[getCount] ;
        int index = 0 ;
        LFU lfu = new LFU(k) ;
        for(int i = 0 ; i < operators.length ; i ++) {
            if(operators[i].length == 2) {
                res[index ++] = lfu.get(operators[i][1]) ;
            } else {
                lfu.set(operators[i][1] , operators[i][2]) ;
            }
        }
        return res ;
    }
}