用最容易理解的方法，实现LRU、LFU算法
目录
1、LRU
1.1、问题描述：
1.2、解题思路：使用LinkedHashMap实现
2、LFU
2.1、问题描述：
2.2、解题思路：使用LinkedHashMap
1、LRU
1.1、问题描述：
题目：可参考牛客：设计LRU缓存结构_牛客题霸_牛客网
问题概述：实现一个类，这个类需要做以下几件事情：
- 类实例化后，可以存储key、value的键值对；
- 存储的键值对数是有限的，当数量达到上限后，就会删除最久未访问过的键值对
- 实现一个get方法，可以通过key，获取到value的值（这也算是一次访问）
- 实现一个set方法，可以将key，value存放进去（若key存在，则更新value值）
- 要求get、set方法的时间复杂度为O(1)
1.2、解题思路：使用LinkedHashMap实现
首先，我们其实可以理解为，我们现在是需要一个map的，来存储key、value，例如我们可以使用HashMap或者是TreeMap，因为要求get、set方法的时间复杂度为O(1)，所以我们选择HashMap~
其次呢，我们还要记录map进去的键值对的顺序的，所以很显然，我们可以选择LinkedHashMap。LinkedHashMap的底层其实就是：维护着一个HashMap：key、value在HashMap中存储着；还维护着一个双向链表：key、value在链表中也会有自己的位置 - 维护他的顺序（key、value以Node节点存在，有pre指针、next指针）~
我们可以进入LinkedHashMap源码中看看：
接下来就是代码实现了，还是很容易理解的：
import java.util.*;public class Solution {LinkedHashMap<Integer, Integer> map;int cacapacity = 0;//长度int size = 0;public Solution(int capacity) {// write code herethis.cacapacity = capacity;this.map = new LinkedHashMap<>(capacity);}public int get(int key) {// write code hereInteger value = map.get(key);if(value == null){return -1;} else {map.remove(key);map.put(key, value);return value;}}public void set(int key, int value) {// write code hereif(map.containsKey(key)){map.remove(key);map.put(key, value);} else {if(size < cacapacity){map.put(key ,value);size++;} else if(size == cacapacity){int first = map.keySet().iterator().next();map.remove(first);map.put(key, value);}}return;}
}/*** Your Solution object will be instantiated and called as such:* Solution solution = new Solution(capacity);* int output = solution.get(key);* solution.set(key,value);*/2、LFU
2.1、问题描述：
题目：可参考牛客：设计LFU缓存结构_牛客题霸_牛客网
问题概述：实现一个类，这个类需要做以下几件事情：
- 类实例化后，可以存储key、value的键值对；
- 存储的键值对数是有限的，当数量达到上限后，就会删除访问次数最少得键值对（访问次数一样，则删除最久未被访问的）
- 实现一个get方法，可以通过key，获取到value的值（这也算是一次访问）
- 实现一个set方法，可以将key，value存放进去（若key存在，则更新value值）
2.2、解题思路：使用LinkedHashMap
首先，我们其实可以理解为，我们现在是需要一个map的，来存储key、value，例如我们可以使用HashMap或者是TreeMap，我们继续选择HashMap~
其次呢，我们需要对这些键值对进行排序，排序规则：访问次数从小到大排序，访问次数相同时，则按照访问时间从小到大排序，所以很显然，我们可以选择LinkedHashMap。
思路：
- 使用LinkedHashMap来维护键值对的存储；
- 这里存储时，同时还要记录访问次数，因此，我们map中的存储数据格式采用键：key，值：是一个一维数组，数组第一个值是value值，数组第二个值是访问次数的count值；
- 如果是get，没有则返回-1；有键值对时，记录value值，将原有的键值对删除，调用公共方法再把这个键值加上去，记得count++（公共方法，后面说）；
- 如果是set：
- 先查看这个key是否已存在过，如果key之前不存在：
- 存储的数量未达到上限，键值对的count设为1，调用公共方法新增键值对；
- 存储的数量达到上限，先删除map中第一个key，再调用公共方法新增这组新的键值对；
- 如果key之前就存在：先查询到这个key的count，调用公共方法新增键值对（key，新的value，++count）；
- 先查看这个key是否已存在过，如果key之前不存在：
- 公共方法新增键值对：新增键值对的位置要求：访问次数从小到大排序，访问次数相同时，则按照访问时间从小到大排序，思路：
- 公共方法的参数：原本的LinkedHashMap - 变量map；key、value、count
- 再准备一个备用的LinkedHashMap - 变量设为res，参数中的LinkedHashMap，变量设为map
- 遍历map：
- 如果遍历的count小于等于方法传参中的count，则把这组键值对移到res中
- 如果遍历的count大于方法传参中的count，则先给res新增一组键值对（方法传参中的键值对），停止遍历
- 再遍历map剩余的键值对，将他们转移到res中
注意：看着很复杂，其实就是一些判断而已，主要就是遵循排序规则就可以了
代码如下：
import java.util.*;public class Solution2 {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** lfu design* @param operators int整型二维数组 ops* @param k int整型 the k* @return int整型一维数组*/public static int[] LFU (int[][] operators, int k) {// write code hereLinkedHashMap<Integer, int[]> map = new LinkedHashMap<>(k);int size = 0;ArrayList<Integer> res = new ArrayList<>();for(int i = 0;i<operators.length;i++){//opt = 1,setif(operators[i][0] == 1){// set key:operators[i][1] value:operators[i][2] count:operators - 待定int[] tmp = map.get(operators[i][1]);//新keyif(tmp == null){// 满了if(size == k){Integer first = map.keySet().iterator().next();map.remove(first);//新增进去 todo:map = fun(map, operators[i][1], operators[i][2], 1);} else {//todo:map = fun(map, operators[i][1], operators[i][2], 1);size++;}} else {//旧key,修改value，count todo:map.remove(operators[i][1]);map = fun(map, operators[i][1], operators[i][2], ++tmp[1]);}}else {// getint[] tmp = map.get(operators[i][1]);if(tmp == null){res.add(-1);} else {//记录valueres.add(tmp[0]);//修改次数 todomap.remove(operators[i][1]);map = fun(map, operators[i][1], tmp[0], ++tmp[1]);}}}int[] arr = new int[res.size()];for(int i = 0;i<res.size();i++){arr[i] = res.get(i);}return arr;}//插入 - 整个顺序为-先以count排序，count相同时，插入时间顺序排序public static LinkedHashMap<Integer, int[]> fun(LinkedHashMap<Integer, int[]> map, int key , int value, int count){LinkedHashMap<Integer, int[]> res = new LinkedHashMap<>();int size = 0;int mapSize = map.size();while (size<mapSize){int first = map.keySet().iterator().next();int[] arr = map.get(first);if(arr[1] <= count){res.put(first, arr);map.remove(first);} else {int[] tmp = new int[]{value, count};res.put(key, tmp);break;}size++;}while (size<mapSize){int first = map.keySet().iterator().next();int[] arr = map.get(first);res.put(first, arr);map.remove(first);size++;}//检查新增的key是否成功新增了，如果没有在把他新增在最后面（例如：这组键值对的count最大，就应该在最后一个）if(map.get(key) == null){int[] tmp = new int[]{value, count};res.put(key, tmp);}return res;}public static void main(String[] args) {int[][] arr = {{1,1,1},{1,2,2},{1,3,3},{1,4,4},{2,4},{2,3},{2,2},{2,1},{1,5,5},{2,4}};
// int[][] arr ={{1,1,1},{1,2,2},{2,2}};LFU(arr, 4);}
}