4.5日：LFU缓存
设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和put。
get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。
进阶：你是否可以在 O(1) 时间复杂度内执行两项操作？
分析：HashMap<Integer, Node> cache 存缓存的内容; min 是最小访问频次; HashMap<Integer, LinkedHashSet> freqMap 存每个访问频次对应的Node的双向链表（直接用了JDK现有的LinkedHashSet，其实现了1条双向链表贯穿哈希表中的所有Entry，支持以插入的先后顺序对原本无序的HashSet进行迭代）
class LFUCache{
//存储缓存内容Map<Integer,Node> cache;//存储每个频次对应的双向链表Map<Integer,LinkedHashSet<Node>> freqMap;int size;int capacity;//存储当前最小频次int min;public LFUCache(int capacity){
cache = new HashMap<>(capacity);freMap = new HashMap<>();this.capacity = capacity;}public int get(int key){
Node node = cache.get(key);if (node == null){
return -1;}freqInc(node);return node.value;}public void put(int key,int value){
if (capacity == 0){
return;}Node node = cache.get(key);if (node != null){
node.value = value;freqInc(node);}else{
if (size == capacity){
Node deadNode = removeNode();cache.remove(deadNode.key);size--;}Node newNode = new Node(key,value);cache.put(key,newNode);addNode(newNode);size++;}}void freqInc(Node node){
//从原freq对应的链表里移除，并更新minint freq = node.freq;LinkedHashSet<Node> set = freqMap.get(freq);set.remove(node);if (freq == min && set.size() == 0){
min = freq + 1;}//加入新freq对应的链表node.freq++;LinkedHashSet<Node> newSet = freqMap.get(freq + 1);if (newSet == null){
newSet = new LinkedHashSet<>();freqMap.put(freq + 1,newSet);}set.add(node);min = 1;}Node removeNode(){
LinkedHashSet<Node> set = freqMap.get(min);Node deadNode = set.iterator().next();set.remove(deadNode);return deadNode;}
}class Node{
int key,value;int freq = 1;public Node(){
}public Node(int key,int value){
this.key = key;this.value = value;}
}