LFU缓存结构设计

描述

一个缓存结构需要实现如下功能。

• set(key, value)：将记录(key, value)插入该结构
• get(key)：返回key对应的value值

但是缓存结构中最多放K条记录，如果新的第K+1条记录要加入，就需要根据策略删掉一条记录，然后才能把新记录加入。这个策略为：在缓存结构的K条记录中，哪一个key从进入缓存结构的时刻开始，被调用set或者get的次数最少，就删掉这个key的记录；

如果调用次数最少的key有多个，上次调用发生最早的key被删除

这就是LFU缓存替换算法。实现这个结构，K作为参数给出

[要求]

set和get方法的时间复杂度为O(1)

若opt=1，接下来两个整数x, y，表示set(x, y)
若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1

对于每个操作2，输出一个答案

示例1

输入：

[[1,1,1],[1,2,2],[1,3,2],[1,2,4],[1,3,5],[2,2],[1,4,4],[2,1]],3

返回值：

[4,-1]

说明：在执行”1 2 4”后，”1 1 1”被删除。因此第二次询问的答案为-1

备注：

$1 \leq k \leq n \leq 10^5$

$-2 \times 10^9 \leq x,y \leq 2 \times 10^9$

import java.util.*;


public class Solution {
    /**
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    class LFUCache{
        class Node{
            int k;
            int val;
            int freq;
            public Node(){}
            public Node(int k, int val, int freq){
                this.k = k;
                this.val = val;
                this.freq = freq;
            }
        }
        private int capacity;
        private Map<Integer, Node> map = new HashMap<>();
        private Map<Integer, LinkedList<Node>> freqMap = new HashMap<>();
        private int minFreq;
        public LFUCache(int capacity){
            this.capacity = capacity;
            this.minFreq = 1;
        }
        public void update(Node node){
            LinkedList<Node> list = freqMap.get(node.freq);
            list.remove(node);
            if (list.isEmpty() && node.freq == minFreq){
                minFreq++;
            }
            node.freq++;
            if (!freqMap.containsKey(node.freq)){
                freqMap.put(node.freq, new LinkedList<>());
            }
            freqMap.get(node.freq).addLast(node);
           
        }
        public int get(int k){
            if (!map.containsKey(k)){
                return -1;
            }
            Node node = map.get(k);
            update(node);
            return node.val;
        }
        public void put(int k, int val){
            if (map.containsKey(k)){
                Node node = map.get(k);
                node.val = val;
                update(node);
                map.put(k, node);
                return;
            }
            if (map.size() == capacity){
                Node node = freqMap.get(minFreq).removeFirst();
                map.remove(node.k);
            }
            Node node = new Node(k, val, 1);
            map.put(k, node);
            if (!freqMap.containsKey(1)){
                freqMap.put(1, new LinkedList<>());
            }
            freqMap.get(1).addLast(node);
            minFreq = 1;
        }
    }
     
    public int[] LFU (int[][] operators, int k) {
        // write code here
        LFUCache cache = new LFUCache(k);
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; i < operators.length; i++){
            if (operators[i][0] == 1){
                cache.put(operators[i][1], operators[i][2]);
            }else{
                res.add(cache.get(operators[i][1]));
            }
        }
        int[] ans = new int[res.size()];
        for (int i = 0; i < ans.length; i++){
            ans[i] = res.get(i);
        }
        return ans;
    }
}