LRU 缓存：哈希表 + 双向链表的经典设计

class Node {
    int key, value;
    Node prev, next;
    Node(int k, int v) { key = k; value = v; }
}

public class LRUCache {
    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0);   // 哨兵：头
    private final Node tail = new Node(0, 0);   // 哨兵：尾

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            moveToHead(node);
            return;
        }
        Node fresh = new Node(key, value);
        map.put(key, fresh);
        addToHead(fresh);
        if (map.size() > capacity) {
            Node removed = removeTail();
            map.remove(removed.key);
        }
    }

    // ===== 双向链表操作 =====
    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    private Node removeTail() {
        Node node = tail.prev;
        removeNode(node);
        return node;
    }
}

class LFUCache {
    // ===== 双向链表 =====
    static class DLinkedList {
        Node head = new Node(0, 0), tail = new Node(0, 0);  // 哨兵
        int size = 0;
        DLinkedList() { head.next = tail; tail.prev = head; }

        void addFirst(Node n) {
            n.prev = head;
            n.next = head.next;
            head.next.prev = n;
            head.next = n;
            size++;
        }

        void removeNode(Node n) {
            n.prev.next = n.next;
            n.next.prev = n.prev;
            size--;
        }

        Node removeLast() {
            if (size == 0) return null;
            Node n = tail.prev;
            removeNode(n);
            return n;
        }

        boolean isEmpty() { return size == 0; }
    }

    static class Node {
        int key, value, freq;
        Node prev, next;
        Node(int k, int v) { key = k; value = v; freq = 1; }
    }

    Map<Integer, Node> nodeMap = new HashMap<>();                    // key → 节点
    Map<Integer, DLinkedList> freqMap = new HashMap<>();            // freq → 链表
    int minFreq = 0, capacity;

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

    public int get(int key) {
        if (capacity == 0) return -1;
        Node node = nodeMap.get(key);
        if (node == null) return -1;
        increaseFreq(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (capacity == 0) return;
        Node node = nodeMap.get(key);
        if (node != null) {
            node.value = value;
            increaseFreq(node);
            return;
        }
        if (nodeMap.size() == capacity) {
            // 淘汰 minFreq 链表的尾节点（最久未访问）
            DLinkedList list = freqMap.get(minFreq);
            Node removed = list.removeLast();
            nodeMap.remove(removed.key);
        }
        Node fresh = new Node(key, value);
        nodeMap.put(key, fresh);
        freqMap.computeIfAbsent(1, k -> new DLinkedList()).addFirst(fresh);
        minFreq = 1;
    }

    private void increaseFreq(Node node) {
        int freq = node.freq;
        DLinkedList list = freqMap.get(freq);
        list.removeNode(node);
        if (freq == minFreq && list.isEmpty()) minFreq++;
        node.freq++;
        freqMap.computeIfAbsent(node.freq, k -> new DLinkedList()).addFirst(node);
    }
}

// 有哨兵时：不用判断 head/tail 是不是 null
private void addToHead(Node node) {
    node.prev = head;
    node.next = head.next;
    head.next.prev = node;
    head.next = node;
}

public class LRUCache extends LinkedHashMap<Integer, Integer> {
    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);     // accessOrder = true
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }
}