设计LFU缓存结构

LFU与LRU相似，只不过当容量超出时，需要删除最近最不常使用。因此使用map来记录每个频率对应的LRU的链表，则删除元素时，只需要删除队头元素即可。

import java.util.*;
public class Solution {
    class Node {
        int key, value, frequency;
        Node(int k, int v) {
            this.key = k;
            this.value = v;
            this.frequency = 1;
        }
    }
    private Map cache;
    private Map> frequencyMap;  // 根据频率记录 每个频率对应的LRU 链表
    private int capacity;
    private int minFrequency;
    public int[] LFU(int[][] operators, int k) {
        this.capacity = k;
        this.cache = new HashMap();  // 记录所有节点
        this.frequencyMap = new HashMap();
        List result = new ArrayList();
        for (int[] operator : operators) {
            if (operator[0] == 1) {
                this.set(operator[1], operator[2]);
            } else if (operator[0] == 2) {
                Node node = get(operator[1]);
                result.add(node == null ? -1 : node.value);
            }
        }
        return result.stream().mapToInt(Integer::intValue).toArray();
    }
    private void set(int key, int value) {
        if (capacity == 0) return;
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            node.value = value;  // 更新一下value
            this.get(key); // 调用一下get 更新频率 逻辑写在 get里面了
            return;
        }
        if (cache.size() >= capacity) {
            evictLFU();  // 删除最少 最常不使用
        }
        Node newNode = new Node(key, value);
        this.cache.put(key, newNode);
        this.frequencyMap.computeIfAbsent(1, k -> new LinkedHashSet()).add(newNode);
        minFrequency = 1;
    }
    private Node get(int key) {
        if (!this.cache.containsKey(key)) return null;
        Node node = cache.get(key);
        int freq = node.frequency;
        this.frequencyMap.get(freq).remove(node);
        if (this.frequencyMap.get(freq).isEmpty()) {
            this.frequencyMap.remove(freq);
            if (minFrequency == freq) { // 更新最小频率
                minFrequency++;
            }
        }
        node.frequency++;
        this.frequencyMap.computeIfAbsent(node.frequency,
                                     k -> new LinkedHashSet()).add(node);
        return node;
    }
    private void evictLFU() {
        LinkedHashSet nodes = this.frequencyMap.get(minFrequency);
        Node nodeToEvict = nodes.iterator().next();
        nodes.remove(nodeToEvict);
        if (nodes.isEmpty()) {
            this.frequencyMap.remove(minFrequency);
        }
        this.cache.remove(nodeToEvict.key);
    }
}

public class Solution {
    private int capacity = 0;
    private Map<Integer, Integer> cacheMap = new HashMap<>();
    private Map<Integer, Integer> keyFreqMap = new HashMap<>();
    private Map<Integer, Set<Integer>> freqKeysMap = new TreeMap<>();

    private void set(int key, int value) {
        Integer cacheValue = cacheMap.get(key);
        cacheMap.put(key, value);
        if (cacheValue == null) {
            if (cacheMap.size() > capacity) {
                Map.Entry<Integer, Set<Integer>> minimumFreqEntry =
                    freqKeysMap.entrySet().iterator().next();
                Integer minimumFreqKey = minimumFreqEntry.getValue().iterator().next();
                remove(minimumFreqKey);
            }
        }
        updateFreq(key);
    }

    private int get(int key) {
        Integer cacheValue = cacheMap.get(key);
        if (cacheValue != null) {
            updateFreq(key);
            return cacheValue;
        } else {
            return -1;
        }
    }

    private void remove(int key) {
        cacheMap.remove(key);
        Integer freq = keyFreqMap.remove(key);
        Set<Integer> freqKeys = freqKeysMap.get(freq);
        freqKeys.remove(key);
        if (freqKeys.isEmpty()) {
            freqKeysMap.remove(freq);
        }
    }

    private void updateFreq(int key) {
        Integer freq = keyFreqMap.remove(key);
        if (freq != null) {
            keyFreqMap.put(key, freq + 1);
            Set<Integer> freqKeys = freqKeysMap.get(freq);
            freqKeys.remove(key);
            if (freqKeys.isEmpty()) {
                freqKeysMap.remove(freq);
            }
            freqKeysMap.computeIfAbsent(freq + 1, a -> new LinkedHashSet<>()).add(key);
        } else {
            keyFreqMap.put(key, 1);
            freqKeysMap.computeIfAbsent(1, a -> new LinkedHashSet<>()).add(key);
        }
    }

    public int[] LFU(int[][] operators, int k) {
        capacity = k;
        int resultNum = (int) Arrays.stream(operators).filter(arr -> arr[0] ==
                        2).count();
        int[] resultArray = new int[resultNum];
        for (int i = 0, j = 0; i < operators.length; i++) {
            int[] nums = operators[i];
            int operateType = nums[0];
            if (operateType == 1) {
                set(nums[1], nums[2]);
            } else {
                resultArray[j++] = get(nums[1]);
            }
        }
        return resultArray;
    }
}

    public int[] LFU (int[][] operators, int k) {
        // write code here
        ArrayList<Integer> res=new ArrayList<>();
        Map<Integer,Integer> m1=new LinkedHashMap<>(); // 记录key value
        Map<Integer,Integer> m2=new LinkedHashMap<>(); // 记录key的先后及次数
        for(int i=0;i<operators.length;i++){
            int opt=operators[i][0];
            int key=operators[i][1];
            if(opt==1){
                int val=operators[i][2];
                if(m2.containsKey(key)){ // 写和读都要判断是否已存在
                    int cnt=m2.get(key)+1;
                    m2.remove(key);
                    m1.put(key,val);
                    m2.put(key,cnt);
                }else{
                    if(m1.size()==k){
                        Iterator<Map.Entry<Integer,Integer>> iter=m2.entrySet().iterator();
                        int cnt=Integer.MAX_VALUE ,dk=0;
                        while(iter.hasNext()){
                            Map.Entry<Integer,Integer> entry=iter.next();
                            if(entry.getValue()<cnt){
                                cnt=entry.getValue();
                                dk=entry.getKey();
                            }
                        }
                        m1.remove(dk);
                        m2.remove(dk);
                    }
                    m1.put(key,val);
                    m2.put(key,1);
                }
            }else{
                if(m2.containsKey(key)){
                    int cnt=m2.get(key)+1;
                    m2.remove(key);
                    m2.put(key,cnt);
                }
                res.add(m1.getOrDefault(key,-1));
            }
        }
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }

public class Solution {

    private int capacity;

    private Map<Integer, Node> viewCache = new HashMap<>();

    private Map<Integer, Node> cache = new HashMap<>();

    private ArrayList<Integer> result = new ArrayList<>();

    private int minFreq = 1;

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LFU (int[][] operators, int k) {
        this.capacity = k;
        for (int[] operator:operators) {
            handleOpt(operator);
        }
        return listToArray(result);
    }

    private void handleOpt(int[] operator) {
        int optType = operator[0];
        switch (optType) {
            case 1:
                set(operator[1], operator[2]);
                break;
            case 2:
                result.add(get(operator[1]));
                break;
        }
    }

    private int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        Node node = cache.get(key);
        node.freq += 1;
        handleFreq(node);
        return node.value;
    }

    private void set(int key, int value) {
        Node node ;
        if (!cache.containsKey(key)) {
            checkSize();
            node = new Node (key, value);
            cache.put(key, node);
            minFreq = node.freq;
        } else {
            node = cache.get(key);
            node.value = value;
            node.freq += 1;
        }
        handleFreq(node);
    }

    private void handleFreq(Node node) {
        //浏览次数变更，节点去除（完成上下节点的交接，清除与上下节点的指向）
        clearPointer(node);
        //如果存在相同浏览次数的节点，放在节点尾部
        if (viewCache.containsKey(node.freq)) {
            Node head = viewCache.get(node.freq);
            while (head.next != null) {
                head = head.next;
            }
            head.next = node;
            node.pre = head;
            return;
        }
        //不存在这个浏览次数的节点，新建key
        viewCache.put(node.freq, node);
    }

    private void clearPointer(Node node) {
        Node pre = node.pre;
        Node next = node.next;
        if (pre != null) {
            pre.next = next;
        }
        if (next != null) {
            next.pre = pre;
        }
        if (viewCache.get(node.freq - 1) == node) {
            if (next != null) {
                viewCache.put(node.freq - 1, next);
            } else {
                viewCache.remove(node.freq - 1);
                if (node.freq - 1 == minFreq) {
                    minFreq = node.freq;
                }
            }
        }
        node.next = null;
        node.pre = null;
    }

    private void checkSize() {
        if (cache.size() < capacity) {
            return;
        }
        Node node = viewCache.get(minFreq);
        int key = node.key;
        if (node.next != null) {
            node = node.next;
            node.pre = null;
            viewCache.put(minFreq, node);
        } else {
            viewCache.remove(minFreq);
            minFreq++;
        }
        cache.remove(key);
    }

    private int[] listToArray(ArrayList<Integer> list) {
        int[] output = new int[result.size()];
        for (int i = 0; i < list.size(); i++ ) {
            output[i] = list.get(i);
        }
        return output;
    }

    class Node {
        int key;
        int value;
        int freq;
        Node pre;
        Node next;

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

}

import java.util.*;
public class Solution {
    //使用两个哈希表，一个用来存储元素，另一个用来存储元素被调用的次数
    //如果hash1.size()<k ,可以set直接set，如果hash1.size()==k,要先删除count最小的元素，然后再set
     LinkedHashMap<Integer,Integer> hash1=new LinkedHashMap<>(); //key,value
     LinkedHashMap<Integer,Integer> hash2=new LinkedHashMap<>(); //key,count
     private int k;  //容量大小
    public int[] LFU (int[][] operators, int k) {
        this.k=k;
        int resLen=(int)Arrays.stream(operators).filter(x->x[0]==2).count();//提前确定结果数组的长度
        int[] result=new int[resLen]; //对于每个操作2，返回一个答案放进结果数组
        int num=0;
        for(int[] op: operators){
            if(op[0]==1){ //set 
                setEle(op[1],op[2]);
            }else if(op[0]==2){
                 int r= getEle(op[1]);
                result[num++]=r;
            }
        }
        return result;
    }
    public void setEle(int key,int value){
        //往结构里放入元素 ,添加元素，元素会有变化，先判断hash1表里能不能找到key，有的话，就属于更新元素，count+1
        // 如果hash1里没有，就是新元素，判断hash1.size()如果不是<k,就要删除一个元素再添加
        if(hash1.containsKey(key)){ //hash1表里有的，hash2表里一定也有
            hash1.put(key,value);//会覆盖value
            int val=hash2.get(key)+1;
            hash2.remove(key);
            hash2.put(key,val);
            //hash2.put(key,hash2.get(key)+1);
        }else{
            if(hash1.size()==k){
                int delkey=findMin();
                hash1.remove(delkey); //同步删除hash1和hash2表的调用次数最少的元素
                hash2.remove(delkey);
            }
            hash1.put(key,value);
            hash2.put(key,1);
        }
        
    }
    public int getEle(int key){
        //根据传入的key值查找元素.查找元素，不会导致元素有变化，所以就是直接从hash1里找，找不到就返回-1
        if(hash1.containsKey(key)){
            int val=hash2.get(key)+1;
            hash2.remove(key);
            hash2.put(key,val); //这里是利用LinkedHashMap的有序排序特性,每次调用就把key和count放到后面
            return hash1.get(key);
        }else{
            return -1;
        }
        
    }
    public int findMin(){
        int min=Integer.MAX_VALUE;
        int res=0;
        //返回count最小的元素的key值
        Set<Integer> keys=hash2.keySet(); //从LinkedHashMap前到后遍历，最前面的就算最早被调用的记录
        for(int key:keys){        //用来处理删除多个调用次数一样的元素，要删除上次调用发生最早的记录
            int count=hash2.get(key);
            if(count<min){
                min=count;
                res=key;
            }
        }
        return res;
    }
}

    Map<Integer, Integer> valueMap;
    LinkedHashMap<Integer, Integer> countMap;

    public int[] LFU(int[][] operators, int k) {
        // write code here
        int size = 0;
        valueMap = new HashMap<>(k);
        countMap = new LinkedHashMap<>(k);
        ArrayList<Integer> list = new ArrayList<>();
        //校验operators
        int length = operators.length;
        for (int i = 0; i < length; i++) {
            int[] curr = operators[i];
            if (curr[0] == 1) {
                if (!valueMap.containsKey(curr[1]) && size >= k) {
                    int min = Integer.MAX_VALUE, key = min;
                    Set<Map.Entry<Integer, Integer>> entries = countMap.entrySet();
                    for (Map.Entry<Integer, Integer> entry : entries) {
                        if (min > entry.getValue()) {
                            min = entry.getValue();
                            key = entry.getKey();
                        }
                    }
                    Map.Entry<Integer, Integer> first = entries.iterator().next();
                    if (first.getValue() == min){
                        key = first.getKey();
                    }
                    valueMap.remove(key);
                    countMap.remove(key);
                    size--;
                }
                this.set(curr[1], curr[2]);
                size++;
            } else {
                list.add(this.get(curr[1]));
            }
        }
        return list.stream().mapToInt(x -> x).toArray();
    }

    public int get(int x) {
        int value = valueMap.getOrDefault(x, -1);
        if (value != -1) {
            int count = countMap.get(x);
            countMap.remove(x);
            countMap.put(x, count + 1);
        }
        return value;
    }

    public void set(int x, int y) {
        countMap.put(x, countMap.getOrDefault(x, 0) + 1);
        valueMap.put(x, y);
    }

import java.util.*;


public class Solution {
   
    public int[] LFU (int[][] operators, int k) {
        // hashMap和priorityQueue保存，hashMap存调用次数和计时，priorityQueue排序
        HashMap<Integer,Node> count=new HashMap<>();//对key计数，key=operators[i][1],value=node node.count计数 node.time 计时
        HashMap<Integer,int[]> temp=new HashMap<>(); //保存key(operators[i][1])和operators[i]的映射，好方便找出value值
        PriorityQueue<Integer> minHeap=new PriorityQueue<>((o1,o2)->count.get(o1).count.equals(count.get(o2).count)?
            count.get(o1).time.compareTo(count.get(o2).time):count.get(o1).count.compareTo(count.get(o2).count));//优先队列，取count值较小的，count值一致时取time小的
        ArrayList<Integer> res=new ArrayList<>();
        int time=0;
        for(int i=0;i<operators.length;i++){
            if(operators[i][0]==1){
                if(temp.size()==k){
                    int poll=minHeap.poll(); //把调用次数最少的poll掉
                    count.remove(poll);
                    temp.remove(poll);
                }
                //插入temp和count
                temp.put(operators[i][1],operators[i]);
                if(count.containsKey(operators[i][1])){
                    Node node=new Node(count.get(operators[i][1]).count+1,time++);
                    count.put(operators[i][1],node);
                    minHeap.remove(operators[i][1]);
                    minHeap.offer(operators[i][1]);
                }else{
                    Node node1=new Node(1,time++);
                    count.put(operators[i][1],node1);
                    minHeap.offer(operators[i][1]);
                }
            }else if(operators[i][0]==2){
                if(temp.get(operators[i][1])==null){
                    res.add(-1);
                }else{
                    int[] operator=temp.get(operators[i][1]);
                    res.add(operator[2]);
                    if(count.containsKey(operators[i][1])){
                      Node node2=new Node(count.get(operators[i][1]).count+1,time++);
                    count.put(operators[i][1],node2);
                         minHeap.remove(operators[i][1]);
                        minHeap.offer(operators[i][1]);
                    }else{  
                        Node node3=new Node(1,time++);
                        count.put(operators[i][1],node3);
                        minHeap.offer(operators[i][1]);
                    }
                    
                }
            }
        }
        int[] result=new int[res.size()];
        for(int i=0;i<res.size();i++){
            result[i]=res.get(i);
        }
        return result;
    }
}

class Node{
    public Integer count;
    public Integer time;
    
    public Node(Integer count,Integer time){
        this.count=count;
        this.time=time;
    }
}

import java.util.*;
public class Solution {
    public int[] LFU (int[][] operators, int k) {
        // write code here
        LinkedHashMap<Integer,Integer> map=new LinkedHashMap<>();
        LinkedHashMap<Integer,Integer> num=new LinkedHashMap<>();
        ArrayList<Integer> list=new ArrayList<>();
            
        for(int[] i:operators)
        {
            int op=i[0],key=i[1];
                
            if(op==1)
            {
                if(map.size()==k)
                {   
                    int leastnumkey=(int)getMinKey(num);
                    map.remove(leastnumkey);
                    num.remove(leastnumkey);
                }                                         //若满，则移除表中最不常用的
                int count=0;
                map.put(key,i[2]);                       //未满，添加或者覆盖
                num.put(key,count);
            }
            if(op==2)
            {
                if(map.containsKey(key))
                {
                          int count=num.get(key);
                          num.put(key,count+1);//覆盖
                          int val=map.remove(key);
                          map.put(key,val);//不要忘记将改key设为最常用的
                          list.add(val);//弹出到list
                }
                else
                    list.add(-1);
            }
                
        }
        int[] arr=new int[list.size()];//将arrylist变为数组形式返回
        for(int i=0;i<arr.length;i++)
            arr[i]=list.get(i);
        return arr;
    }
        
//     public static Object getMinKey(LinkedHashMap<Integer, Integer> map) {
//         if (map == null) return null;
//         Set<Integer> set = map.keySet();
//         Object[] obj = set.toArray();
//         //Arrays.sort(obj);
//         return obj[0];//(此方法太大，运行超时)
//          }
   public static Object getMinKey(Map<Integer, Integer> map) {
        int minkey = 0,  min = Integer.MAX_VALUE;
        for(Map.Entry<Integer, Integer> entry: map.entrySet()) {
            if(entry.getValue() < min) {
                min = entry.getValue();
                minkey = entry.getKey();
            }
        }
        return minkey;
    }
    
}

import java.util.*;


public class Solution {
    /**
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LFU (int[][] operators, int k) {
        // write code here
        Map<Integer, Integer[]> map = new LinkedHashMap<>(k);
        List<Integer> res = new ArrayList<>();
        for(int [] ops: operators) {
            if(ops[0] == 1) {
                // set
                set(map, ops[1], ops[2], k);
            }else if(ops[0] == 2) {
                // get
                res.add(get(map, ops[1]));
            }
        }
         int[] arr=new int[res.size()];//将arrylist变为数组形式返回
        for(int i=0;i<arr.length;i++)
            arr[i]=res.get(i);
        return arr;
    }
    
    // set
    private void set(Map<Integer, Integer[]> map, int key, int val, int cap) {
        if(map.size() == cap) {
            remove(map);
        }
            map.put(key, new Integer[]{val, 1});
        
    }
    
    // get
    private Integer get(Map<Integer, Integer[]> map, int key) {
        Integer[] value = map.get(key);
        if(value == null) {
            return -1;
        }else {
            map.put(key, new Integer[]{value[0], value[1] + 1});
            return value[0];
        }
    }
    
    // remove
    private void remove(Map<Integer, Integer[]> map) {
        int key = 0,  min = Integer.MAX_VALUE;
        for(Map.Entry<Integer, Integer[]> entry: map.entrySet()) {
            if(entry.getValue()[1] < min) {
                min = entry.getValue()[1];
                key = entry.getKey();
            }
        }
        map.remove(key);
    }
}

	

import java.util.*;


public class Solution {
    /**
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    Map<Integer,Integer[]>map=new LinkedHashMap<>();
    public int[] LFU (int[][] operators, int k) {
        List<Integer>res=new ArrayList<>();
        for(int[]op:operators){
            if(op[0]==1){//set(x,y)
                set(op[1],op[2],k);
            }
            else if(op[0]==2){//get(x)
               res.add(get(op[1]));
            }
            
        }
        int n=res.size();
        int[]result=new int[n];
        for(int i=0;i<n;i++) result[i]=res.get(i);
        return result;
       
    }
    public int get(int key){
        if(map.containsKey(key)) {
            Integer[]val=map.get(key);
            map.put(key,new Integer[]{val[0],val[1]+1});
            return val[0];
        }
        else return -1;
    }
    public void set(int key,int value,int cap){
        if(map.size()==cap){
            removeMin();
        }
        
        if(map.containsValue(key)){
            Integer[]arr=map.get(key);
            map.put(key,new Integer[]{value,arr[1]+1});//次数+1
        }
        else map.put(key,new Integer[]{value,1});
        
    }
    public void removeMin(){//删除map中time最小的元素
        int minKey=0,minTime=Integer.MAX_VALUE;
        for(Integer key:map.keySet()){
            Integer[]arr=map.get(key);
            if(arr[1]<minTime){
                minTime=arr[1];
                minKey=key;
            }
        }
        map.remove(minKey);
    }

}