最近刷力扣题，对于我这种 0 基础来说，真的是脑壳疼啊。这个月我估计都是中等和困难题，没有简单题了。
幸好，力扣上有各种大牛给写题解。看着他们行云流水的代码，真的是羡慕不已。让我印象最深刻的就是人称 “甜姨” 的知心姐姐，还有名叫威哥的大哥。几乎每天他们的题解我都是必看的。
甜姨的题解，虽然姿势很帅，但是对于我这种新手来说，感觉不是太友好，因为思路写的太少，不是很详细。所以，每次我看不明白的时候，都得反复看好几遍，才能想明白她代码中的思路。
上个周末的一道题是，让实现一个 LFU 缓存算法。经过我几个小时的研究（其实，应该有8个小时以上了，没得办法啊，菜就得多勤奋咯），终于把甜姨的思路整明白了。为了便于以后自己复习，就把整个思路记下来了，并配上图示和大量代码注释，我相信对于跟我一样的新手来说，是非常友好的。
经过甜姨同意，参考来源我也会贴出来：https://leetcode-cn.com/problems/lfu-cache/solution/java-13ms-shuang-100-shuang-xiang-lian-biao-duo-ji/
虽然，力扣要求是用时间复杂度 O(1) 来解，但是其它方式我感觉也有必要了解，毕竟是一个由浅到深的过程，自己实现一遍总归是好的。因此，我就把五种求解方式，从简单到复杂，都讲一遍。
LFU实现力扣原题描述如下：
请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。 get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。 put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近 最少使用的键。 「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。 示例： LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 去除 key 2 cache.get(2); // 返回 -1 (未找到key 2) cache.get(3); // 返回 3 cache.put(4, 4); // 去除 key 1 cache.get(1); // 返回 -1 (未找到 key 1) cache.get(3); // 返回 3 cache.get(4); // 返回 4 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/lfu-cache就是要求我们设计一个 LFU 算法，根据访问次数（访问频次）大小来判断应该删除哪个元素，get和put操作都会增加访问频次。当访问频次相等时，就判断哪个元素是最久未使用过的，把它删除。
因此，这道题需要考虑两个方面，一个是访问频次，一个是访问时间的先后顺序。
方案一：使用优先队列思路：
我们可以使用JDK提供的优先队列 PriorityQueue 来实现 。 因为优先队列内部维护了一个二叉堆，即可以保证每次 poll 元素的时候，都可以根据我们的要求，取出当前所有元素的最大值或是最小值。只需要我们的实体类实现 Comparable 接口就可以了。
因此，我们需要定义一个 Node 来保存当前元素的访问频次 freq，全局的自增的 index，用于比较大小。然后定义一个 Map<Integer,Node> cache ，用于存放元素的信息。
当 cache 容量不足时，根据访问频次 freq 的大小来删除最小的 freq 。若相等，则删除 index 最小的，因为index是自增的，越大说明越是最近访问过的，越小说明越是很长时间没访问过的元素。
因本质是用二叉堆实现，故时间复杂度为O(logn)。
public class LFUCache4 { public static void main(String[] args) { LFUCache4 cache = new LFUCache4(2); cache.put(1, 1); cache.put(2, 2); // 返回 1 System.out.println(cache.get(1)); cache.put(3, 3); // 去除 key 2 // 返回 -1 (未找到key 2) System.out.println(cache.get(2)); // 返回 3 System.out.println(cache.get(3)); cache.put(4, 4); // 去除 key 1 // 返回 -1 (未找到 key 1) System.out.println(cache.get(1)); // 返回 3 System.out.println(cache.get(3)); // 返回 4 System.out.println(cache.get(4)); } //缓存了所有元素的node Map<Integer,Node> cache; //优先队列 Queue<Node> queue; //缓存cache 的容量 int capacity; //当前缓存的元素个数 int size; //全局自增 int index = 0; //初始化 public LFUCache4(int capacity){ this.capacity = capacity; if(capacity > 0){ queue = new PriorityQueue<>(capacity); } cache = new HashMap<>(); } public int get(int key){ Node node = cache.get(key); // node不存在，则返回 -1 if(node == null) return -1; //每访问一次，频次和全局index都自增 1 node.freq++; node.index = index++; // 每次都重新remove，再offer是为了让优先队列能够对当前Node重排序 //不然的话，比较的 freq 和 index 就是不准确的 queue.remove(node); queue.offer(node); return node.value; } public void put(int key, int value){ //容量0，则直接返回 if(capacity == 0) return; Node node = cache.get(key); //如果node存在，则更新它的value值 if(node != null){ node.value = value; node.freq++; node.index = index++; queue.remove(node); queue.offer(node); }else { //如果cache满了，则从优先队列中取出一个元素，这个元素一定是频次最小，最久未访问过的元素 if(size == capacity){ cache.remove(queue.poll().key); //取出元素后，size减 1 size--; } //否则，说明可以添加元素，于是创建一个新的node，添加到优先队列中 Node newNode = new Node(key, value, index++); queue.offer(newNode); cache.put(key,newNode); //同时，size加 1 size++; } } //必须实现 Comparable 接口才可用于排序 private class Node implements Comparable<Node>{ int key; int value; int freq = 1; int index; public Node(){ } public Node(int key, int value, int index){ this.key = key; this.value = value; this.index = index; } @Override public int compareTo(Node o) { //优先比较频次 freq，频次相同再比较index int minus = this.freq - o.freq; return minus == 0? this.index - o.index : minus; } } } 方案二：使用一条双向链表思路：