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

使用LinkedHashMap,每次调用之后，删除再加入这个K-V，就能保证是最新操作的在前面了。需要注意的是，每次操作put操作需要分成三个类别：1、k已存在；2、k不存在且未达到最大容量；3、k不存在且已经达到最大容量。其中第三种需要找出最少使用且最久的Bolck（笔者在这里没有使用O(lgn)的方法）。这个其实可以用一个minUsedKey来做记录（思路和最小栈一致），这样的话，可以在O（lgn)时间内，感兴趣的读者可以自行实现。

public class Solution {
    class Block{
        int u;
        int k;
        int v;
        Block(int u,int k,int v){
            this.u = u;this.k=k;this.v=v;
        }
    }
    class Cache{
        int size;
        int maxSize;
        Map<Integer,Block>  map = new LinkedHashMap<>();
        Cache(int maxSize){
            this.maxSize = maxSize;
        }
        public int get(int k){
            if(this.map.containsKey(k)){
                Block b = this.map.get(k);
                b.u+=1;
                map.remove(k);
                map.put(k,b);
                return b.v;
            }
            else return -1;
        }
        public void put(int k,int v){
            if(map.containsKey(k)){
                Block b = map.get(k);
                b.v = v;
                b.u +=1;
                map.remove(k);
                map.put(k,b);
            }else {
                if(this.map.size()<this.maxSize){
                    this.map.put(k,new Block(1,k,v));
                }
                else {
                    List<Block> templist = new ArrayList<>(this.map.values());
                    int min = templist.get(0).u;
                    int minKey = templist.get(0).k;
                    for(int i=1;i<templist.size();++i){
                        if(templist.get(i).u<min){
                            minKey = templist.get(i).k;
                        }
                    }
                    this.map.remove(minKey);
                    this.map.put(k,new Block(1,k,v));
                }
            }
        }
    }
    public int[] LFU (int[][] operators, int k) {
        List<Integer> getOpt =new ArrayList<>();
        Cache cache = new Cache(k);
        for(int i=0;i<operators.length;++i){
            if(operators[i][0]==1){
                cache.put(operators[i][1],operators[i][2]);
            }else getOpt.add(cache.get(operators[i][1]));
        }
        int res [] = new int [getOpt.size()];
        for(int i=0;i<res.length;++i)res[i] = getOpt.get(i);
        return res;
    }
    
}