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

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
        int count = 0;
        for(int[] opera : operators){
            if(opera[0] == 2){
                count++;
            }
        }
        int[] res = new int[count];
        LFUCache lfu = new LFUCache(k);
        int index = 0;
        for(int[] opera : operators){
            if(opera[0] == 1){
                lfu.set(opera[1],opera[2]);
            }else{
                int val = lfu.get(opera[1]);
                res[index++] = val;
            }
        }
        return res;
    }
}

class LFUCache{
    class Node{
        int val;
        int key;
        int freq = 1;
        Node next;
        Node pre;
        public Node(){};
        public Node(int key,int val){
            this.val = val;
            this.key = key;
        }
    }
    
    class DoubleLinkedList{
        Node head;
        Node tail;
        DoubleLinkedList(){
            head = new Node();
            tail = new Node();
            head.next = tail;
            tail.pre = head;
        }
        public void addNode(Node node){
            node.next = head.next;
            head.next.pre = node;
            node.pre = head;
            head.next = node;
        }
        
        public void removeNode(Node node){
            node.next.pre = node.pre;
            node.pre.next = node.next;
        }
    }
    
    
    
    
    Map<Integer,Node> cache;
    Map<Integer,DoubleLinkedList> freqMap;
    int min;
    int capacity;
    public LFUCache(int capacity){
        cache = new HashMap<>(capacity);
        freqMap = new HashMap<>();
        this.capacity = capacity;
    }
    
    public int get(int key){
        if(!cache.containsKey(key)){
            return -1;
        }
        Node node = cache.get(key);
        freqInc(node);
        return node.val;
    }
    public void set(int key,int val){
        if(!cache.containsKey(key)){
            if(cache.size() == capacity){
                DoubleLinkedList list = freqMap.get(min);
                cache.remove(list.tail.pre.key);
                list.removeNode(list.tail.pre);
            }
            Node newNode = new Node(key,val);
            cache.put(key,newNode);
            DoubleLinkedList newList = freqMap.get(1);
            if(newList == null){
                newList = new DoubleLinkedList();
                freqMap.put(1,newList);
            }
            newList.addNode(newNode);
            min = 1;
        }else{
            Node node = cache.get(key);
            node.val = val;
            freqInc(node);
        }
    }
    public void freqInc(Node node){
        int freq = node.freq;
        DoubleLinkedList list = freqMap.get(freq);
        list.removeNode(node);
        if(freq == min && list.head.next == list.tail){
            min = freq + 1;
        }
        node.freq++;
        DoubleLinkedList newList = freqMap.get(node.freq);
        if(newList == null){
            newList = new DoubleLinkedList();
            freqMap.put(node.freq,newList);
        }
        newList.addNode(node);
    }
}