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

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

class LFU {
    static class Node {
        int freq;
        int key;
        int value;
        public Node (int freq, int key, int value) {
            this.freq = freq;
            this.key = key;
            this.value = value;
        }
    }

    // 对应节点key值->对应节点的map
    Map<Integer, Node> mp = new HashMap<>();
    // 对应节点频率值->对应节点的双向链表的map
    Map<Integer, LinkedList<Node>> freq_mp = new HashMap<>();

    int size = 0;
    int min_freq = 1;
    int capacity = 0;

    public LFU (int capacity) {
        this.capacity = capacity;
    }

    public void set(int key, int value) {
        // 先看有没有
        Node node = mp.get(key);
        if (node == null) {
            // 不存在这个节点
            // 看当前容量是否足够
            if (size < capacity) {
                // 足够，放进来
                LinkedList<Node> list = freq_mp.get(1);
                Node newNode = new Node(1, key, value);
                min_freq = 1;
                mp.put(key, newNode);
                if (list == null) {
                    freq_mp.put(1, new LinkedList<>());
                    list = freq_mp.get(1);
                }
                list.offer(newNode);
                size++;

            } else {
                // 不够，则将最近最少使用的移出去，然后再把新的放进来
                LinkedList<Node> list = freq_mp.get(min_freq);
                Node old = list.poll();
                if (old == null) {
                    // 这里，old可能为null，为什么？
                    // 因为min_freq有可
                    // 错误
                    System.out.println("min_freq = " + min_freq);
                    System.out.println("error");
                    return;
                }
                mp.remove(old.key);
                Node newNode = new Node(1, key, value);
                min_freq = 1;
                mp.put(key, newNode);
                list = freq_mp.get(1);
                if (list == null) {
                    freq_mp.put(1, new LinkedList<>());
                    list = freq_mp.get(1);
                }
                list.offer(newNode);
            }
        } else {
            // 已经存在这个节点了，则直接set并使其freq+1
            int freq = node.freq;
            freq_mp.get(freq).remove(node);
            if (freq_mp.get(freq).isEmpty()) min_freq += 1;
            node.freq += 1;
            node.value = value;
            LinkedList<Node> list = freq_mp.getOrDefault(freq + 1, new LinkedList<>());
            list.offer(node);
            freq_mp.put(freq + 1, list);
        }
    }

    public int get(int key) {
        Node node = mp.get(key);
        if (node == null) {
            // 无这个节点
            return -1;
        } else {
            // 有这个节点，则其使用freq+1
            int freq = node.freq;
            freq_mp.get(freq).remove(node);
            if (freq_mp.get(freq).isEmpty()) min_freq += 1;
            node.freq += 1;
            LinkedList<Node> list = freq_mp.getOrDefault(freq + 1, new LinkedList<>());
            list.offer(node);
            freq_mp.put(freq + 1, list);
        }
        return node.value;
    }
}

public class Solution {

    public int[] LFU (int[][] operators, int k) {
        LFU lfu = new LFU(k);
        ArrayList<Integer> ans = new ArrayList<>();
        if (operators == null || operators.length == 0) {
            return new int[0];
        }
        for (int[] operator : operators) {
            int key = operator[1];
            switch (operator[0]) {
                case 1:
                    int value = operator[2];
                    lfu.set(key, value);
                    break;
                case 2:
                    ans.add(lfu.get(key));
                    break;
            }
        }
        int[] ansArray = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            ansArray[i] = ans.get(i);
        }
        return ansArray;
    }

    public static void main (String[] args) {
        Solution solution = new Solution();
        int[][] operators = {{1,1,1},{1,2,2},{1,3,2},{1,2,4},{1,3,5},{2,2},{1,4,4},{2,1}};
        int[] ans = solution.LFU(operators, 3);
        for (int i = 0; i < ans.length; i++) {
            System.out.println(ans[i] + " ");
        }
    }
}