设计LRU缓存结构
2023-02-18 16:36:14 时间
题目:
![](https://img2020.cnblogs.com/blog/2168218/202012/2168218-20201223150657580-651209624.png)
思路:
由于set和get方法的时间复杂度为O(1),这就代表着不好用循环,所以应该采用能一次性取出来的方式。如头尾这种方便存取,所以应该一边常用,一边不常用,整体来说,链表结构比较合适。
直接把每次操作的元素塞到链表最末端,这样最后一位就是最常用的,其次,还要想着如何便于一次性检验元素是否在链表中。
代码示例:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedHashMap;
public class Solution {
public static void main(String[] args) {
int[][] operators = {{1, 1, 1}, {1, 2, 2}, {1, 3, 2}, {2, 1}, {1, 4, 4}, {2, 2}};
int k = 3;
int[] result = LRU(operators, k);
System.out.println(Arrays.toString(result));
}
/**
* lru design
*
* @param operators int整型二维数组 the ops
* @param k int整型 the k
* @return int整型一维数组
*/
public static int[] LRU(int[][] operators, int k) {
/**
* 为什么使用LinkedHashMap而不用HashMap?
* 因为使用HashMap,按照插入key的hashcode值进行数组排序的,插入排序,不保证稳定性。
* {1=1, 2=2, 3=2},这里的1=1,如果我先删除了再插入,它依旧是{1=1, 2=2, 3=2},而不是{2=2, 3=2, 1=1}
* 这样就达不到了这里想要的后插入的放在后面越前面的代表最不常用的效果了
* 此外LinkedHashMap是继承于HashMap,拥有同样的方法
*/
LinkedHashMap<Integer, Integer> map = new LinkedHashMap<Integer, Integer>();
//另一方面这里的数组是因为不知道数据的长度,所以采用不限制长度的数组,后面还要对应的转成int[]类型的数组用于输出
ArrayList<Integer> temp = new ArrayList<Integer>();
for (int[] op : operators) {
switch (op[0]) {
case 1:
//判断是否大于长度,是的话要将头结点的最不常用删除,然后再添加新的
if (map.size() > k - 1) {
Iterator iter = map.keySet().iterator();
map.remove(iter.next());
}
map.put(op[1], op[2]);
break;
case 2:
//使用HashMap这类数据有的检验key,判断数据是否存在
//如果存在先将数据取出,再删除,再重新插入,为什么要这么复杂?
//因为思路是复杂度为O(1),如果要排序的话不太合适,直接增删会好一点
if (map.containsKey(op[1])) {
int num = map.get(op[1]);
map.remove(op[1]);
map.put(op[1], num);
temp.add(num);
} else {
temp.add(-1);
}
break;
default:
System.out.println("未知参数");
}
}
int[] result = new int[temp.size()];
int i = 0;
for (int end : temp) {
result[i++] = end;
}
return result;
}
}
相关文章
- Redis中scan命令实战
- [Nginx] 博客园出现了502错误该怎么追查原因
- [MySQL] myisam比innodb查询过程效率探究
- [MySQL]myisam表的索引结构以及查询过程
- [MySQL] innodb表为varchar字段建立索引后的查询过程
- [MySQL] 联合索引最左前缀原则的原因
- [日常] 浏览器前进后退与数据结构的思想
- [PHP] 判断两个数组是否相同
- [PHP] 使用strace排查接口响应速度慢过程
- [PHP] 504 Gateway Time-out处理流程
- [设计模式] 五种创建型设计模式特点
- [设计模式] 设计模式中的七大原则
- [MySQL] mysql 5.5和 5.6 timestamp default 默认值CURRENT_TIMESTAMP问题
- [前端系列] jquery的on事件实现hover函数效果
- [MySQL] mysql优化实例-delete数据不会减少数据文件大小
- [MySQL] mysql优化实例-为join表关联字段增加索引
- 侧边悬浮在线客服咨询按钮-在线客服按钮代码实现
- [前端系列] 解决默认样式-用户代理样式表问题
- [MySQL系列] mysql find_in_set搜索以逗号分隔的字符串
- [前端系列] 解决el-table导致TypeError: this.$el.querySelectorAll is not a function