请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。put(key, value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除最久未使用的键。「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。 进阶：你是否可以在 O(1) 时间复杂度内执行两项操作？ 示例：LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );cache.put(1, 1);cache.put(2, 2);cache.get(1);       // 返回 1cache.put(3, 3);    // 去除 key 2cache.get(2);       // 返回 -1 (未找到key 2)cache.get(3);       // 返回 3cache.put(4, 4);    // 去除 key 1cache.get(1);       // 返回 -1 (未找到 key 1)cache.get(3);       // 返回 3cache.get(4);       // 返回 4

1. put(1, 1),   - 首先查找 nodeMap 中有没有 key=1 对应的 value，       没有就新建 node(key, value, freq) -> node1(1, 1, 1), 插入 nodeMap，{[1, node1]}   - 查找 freqMap 中有没有 freq=1 对应的 value，       没有就新建 doublylinkedlist(head, tail), 把 node1 插入 doublylinkedlist head->next = node1.   如下图，

2. put(2, 2),   - 首先查找 nodeMap 中有没有 key=2 对应的 value，       没有就新建 node(key, value, freq) -> node2(2, 2, 1), 插入 nodeMap，{[1, node1], [2, node2]}   - 查找 freqMap 中有没有 freq=1 对应的 value，       没有就新建 doublylinkedlist(head, tail), 把 node2 插入 doublylinkedlist head->next = node2.   如下图，

3. get(1),   - 首先查找 nodeMap 中有没有 key=1 对应的 value，nodeMap:{[1, node1], [2, node2]},       找到 node1，把 node1 freq+1 -> node1(1,1,2)   - 更新 freqMap，删除 freq=1，node1   - 更新 freqMap，插入 freq=2，node1   如下图，

4. put(3, 3),   - 判断 cache 的 capacity，已满，需要淘汰使用次数最少的元素，找到最小的 freq=1，删除双链表 tail node.prev       如果 tailnode.prev != null, 删除。然后从 nodeMap 中删除对应的 key。   - 首先查找 nodeMap 中有没有 key=3 对应的 value，       没有就新建 node(key, value, freq) -> node3(3, 3, 1), 插入 nodeMap，{[1, node1], [3, node3]}   - 查找 freqMap 中有没有 freq=1 对应的 value，       没有就新建 doublylinkedlist(head, tail), 把 node3 插入 doublylinkedlist head->next = node3.   如下图，

5. get(2)   - 查找 nodeMap，如果没有对应的 key 的 value，返回 -1。6. get(3)   - 首先查找 nodeMap 中有没有 key=3 对应的 value，nodeMap:{[1, node1], [3, node3]},       找到 node3，把 node3 freq+1 -> node3(3,3,2)   - 更新 freqMap，删除 freq=1，node3   - 更新 freqMap，插入 freq=2，node3   如下图，

7. put(4, 4),   - 判断 cache 的 capacity，已满，需要淘汰使用次数最少的元素，找到最小的 freq=1，删除双链表 tail node.prev       如果 tailnode.prev != null, 删除。然后从 nodeMap 中删除对应的 key。   - 首先查找 nodeMap 中有没有 key=4 对应的 value，       没有就新建 node(key, value, freq) -> node4(4, 4, 1), 插入 nodeMap，{[4, node4], [3, node3]}   - 查找 freqMap 中有没有 freq=1 对应的 value，       没有就新建 doublylinkedlist(head, tail), 把 node4 插入 doublylinkedlist head->next = node4.   如下图，

8. get(1)   - 查找 nodeMap，如果没有对应的 key 的 value，返回 -1。9. get(3)   - 首先查找 nodeMap 中有没有 key=3 对应的 value，nodeMap:{[4, node4], [3, node3]},       找到 node3，把 node3 freq+1 -> node3(3,3,3)   - 更新 freqMap，删除 freq=2，node3   - 更新 freqMap，插入 freq=3，node3   如下图，

10. get(4)   - 首先查找 nodeMap 中有没有 key=4 对应的 value，nodeMap:{[4, node4], [3, node3]},       找到 node4，把 node4 freq+1 -> node4(4,4,2)   - 更新 freqMap，删除 freq=1，node4   - 更新 freqMap，插入 freq=2，node4   如下图，

public class LC460LFUCache {  class Node {    int key, val, freq;    Node prev, next;    Node(int key, int val) {      this.key = key;      this.val = val;      freq = 1;    }  }  class DoubleLinkedList {    private Node head;    private Node tail;    private int size;    DoubleLinkedList() {      head = new Node(0, 0);      tail = new Node(0, 0);      head.next = tail;      tail.prev = head;    }    void add(Node node) {      head.next.prev = node;      node.next = head.next;      node.prev = head;      head.next = node;      size++;    }    void remove(Node node) {      node.prev.next = node.next;      node.next.prev = node.prev;      size--;    }    // always remove last node if last node exists    Node removeLast() {      if (size > 0) {        Node node = tail.prev;        remove(node);        return node;      } else return null;    }  }  // cache capacity  private int capacity;  // min frequent  private int minFreq;  Map<Integer, Node> nodeMap;  Map<Integer, DoubleLinkedList> freqMap;  public LC460LFUCache(int capacity) {    this.minFreq = 0;    this.capacity = capacity;    nodeMap = new HashMap<>();    freqMap = new HashMap<>();  }  public int get(int key) {    Node node = nodeMap.get(key);    if (node == null) return -1;    update(node);    return node.val;  }  public void put(int key, int value) {    if (capacity == 0) return;    Node node;    if (nodeMap.containsKey(key)) {      node = nodeMap.get(key);      node.val = value;      update(node);    } else {      node = new Node(key, value);      nodeMap.put(key, node);      if (nodeMap.size() == capacity) {        DoubleLinkedList lastList = freqMap.get(minFreq);        nodeMap.remove(lastList.removeLast().key);      }      minFreq = 1;      DoubleLinkedList newList = freqMap.getOrDefault(node.freq, new DoubleLinkedList());      newList.add(node);      freqMap.put(node.freq, newList);    }  }  private void update(Node node) {    DoubleLinkedList oldList = freqMap.get(node.freq);    oldList.remove(node);    if (node.freq == minFreq && oldList.size == 0) minFreq++;    node.freq++;    DoubleLinkedList newList = freqMap.getOrDefault(node.freq, new DoubleLinkedList());    newList.add(node);    freqMap.put(node.freq, newList);  } }