用最容易理解的方法，实现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 here
this.cacapacity = capacity;
this.map = new LinkedHashMap<>(capacity);
}
public int get(int key) {
// write code here
Integer 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 here
if(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 here
LinkedHashMap<Integer, int[]> map = new LinkedHashMap<>(k);
int size = 0;
ArrayList<Integer> res = new ArrayList<>();
for(int i = 0;i<operators.length;i++){
//opt = 1,set
if(operators[i][0] == 1){
// set key:operators[i][1] value:operators[i][2] count:operators - 待定
int[] tmp = map.get(operators[i][1]);
//新key
if(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 {
// get
int[] tmp = map.get(operators[i][1]);
if(tmp == null){
res.add(-1);
} else {
//记录value
res.add(tmp[0]);
//修改次数 todo
map.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);
}
}