0.问题描述
题目描述
设计LRU缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能
- set(key, value)：将记录(key, value)插入该结构
- get(key)：返回key对应的value值
[要求]
set和get方法的时间复杂度为O(1)
某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的。
当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。
若opt=1，接下来两个整数x, y，表示set(x, y)
若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
对于每个操作2，输出一个答案
样例：
输入：[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3
输出：[1,-1]
1.问题分析
LRU全称是
Least Recently Used，即最近最久未使用的意思。
LRU算法的设计原则是
如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。
思路如下
前面的get和set操作，用Map很容易实现，
难点在于：当`缓存大小`超过K时，如何移除`最不经常使用`的记录，即移除`最久没有被访问`的key和value
找到`最久没有被访问`的key和value 要求
1.知道所有key的`最近`访问时间，能筛选出最小的访问时间
2.获取最小的访问时间对应的key
3.根据key删除
以样例来分析，
输入：[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3（容量）
输出：[1,-1]
[1,1,1] set（1,1）此时缓存为
key value timeInMillis
1 1 1
------------------------------
[1,2,2] set（2,2）此时缓存为
key value timeInMillis
1 1 1
2 2 2
------------------------------
[1,3,2]set（3,2）此时缓存为
key value timeInMillis
1 1 1
2 2 2
3 2 3
------------------------------
[2,1]get（1）key =1存在，返回对应value= 1
此时缓存为
key value timeInMillis
1 1 4
2 2 2
3 2 3
------------------------------
[1,4,4]set（4,4）此次缓存已满
其中timeInMillis最小值对应的key=2，移除相应的key
再执行set（4,4）添加
此时缓存为
key value timeInMillis
1 1 4
3 2 3
4 4 5
------------------------------
[2,2]]get（2）key =2不存在，返回-1， 此时缓存未发生改变
key value timeInMillis
1 1 4
3 2 3
4 4 5
2.问题解决
/**
* lru design
* @param operators int整型二维数组 the ops
* @param k int整型 the k
* @return int整型一维数组
*/
public int[] LRU(int[][] operators, int k) {
//存结果的map
Map<Integer, Integer> keyValueMap = new HashMap<>();
//存最近访问时间的map
//最近访问的时间，key
Map<Long, Integer> timeKeyMap = new HashMap<>();
//key,最近访问的时间
Map<Integer, Long> keyTimeMap = new HashMap<>();
//返回值
ArrayList<Integer> resultArrayList = new ArrayList<>();
long timeInMillis = 1;
for (int[] operator : operators) {
int opt = operator[0];
int key = operator[1];
// 若opt=1，接下来两个整数x, y，表示set(x, y)
// 若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
if (1 == opt) {
int value = operator[2];
//记录新的时间
timeInMillis++;
if (keyValueMap.containsKey(key)) {//已经存在了
//移除旧的入库时间对应的key
Long keyTimeValue = keyTimeMap.get(key);
timeKeyMap.remove(keyTimeValue, key);
timeKeyMap.put(timeInMillis, key);
keyTimeMap.put(key, timeInMillis);
keyValueMap.put(key, value);//更新key对应的value
} else {//不存在了
timeKeyMap.put(timeInMillis, key);
keyTimeMap.put(key, timeInMillis);
keyValueMap.put(key, value);//添加新的key和value
//添加后，超过了最大容量，则直接移除一个
if (keyValueMap.keySet().size() > k) {
Set<Long> longs = timeKeyMap.keySet();
Long minTimes = Collections.min(longs);
Integer minKey = timeKeyMap.get(minTimes);
timeKeyMap.remove(minTimes, minKey);
keyTimeMap.remove(minKey, minTimes);
keyValueMap.remove(minKey);
}
}
} else if (2 == opt) {
if (keyValueMap.containsKey(key)) {//存在
//返回结果
resultArrayList.add(keyValueMap.get(key));
//移除旧的入库时间对应的key
Long keyTimeValue = keyTimeMap.get(key);
timeKeyMap.remove(keyTimeValue, key);
//记录新的时间
timeInMillis++;
timeKeyMap.put(timeInMillis, key);
keyTimeMap.put(key, timeInMillis);
} else {//不存在
//返回结果
resultArrayList.add(-1);
}
}
}
int[] result = new int[resultArrayList.size()];
for (int i = 0; i < resultArrayList.size(); i++) {
Integer integer = resultArrayList.get(i);
result[i] = integer;
}
return result;
}
结果提示通过，但是很明显，太浪费空间了，且看上去很繁琐
3.优化
3.1引入新的数据结构
针对难点：当`缓存大小`超过K时，如何移除`最不经常使用`的记录，即移除`最久没有被访问`的key和value
可以可以考虑用LinkedHashMap
在LinkedHashMap订购模式中设置参数为true
LinkedHashMap<Integer,Integer> map = new LinkedHashMap<>(6,0.75f,true);
表示让 linkedHashMap `按照访问顺序来进行排序`，`最近访问`的放在`尾部`，`最长时间未被访问`的数据的放在`头部`。
3.2代码实现
/**
* lru design
* @param operators int整型二维数组 the ops
* @param k int整型 the k
* @return int整型一维数组
*/
public int[] LRU2(int[][] operators, int k) {
//true 表示让 linkedHashMap 按照访问顺序来进行排序，最近访问的放在尾部，最长时间未被访问的数据的放在头部。
LinkedHashMap<Integer, Integer> urlMap = new LinkedHashMap<Integer, Integer>((int) Math.ceil(k / 0.75) + 1, 0.75f, true);
//返回值
ArrayList<Integer> resultArrayList = new ArrayList<>();
for (int[] operator : operators) {
int opt = operator[0];
int key = operator[1];
if (1 == opt) {//set
// 若opt=1，接下来两个整数x, y，表示set(x, y)
int value = operator[2];
if (urlMap.size() >= k) {//当前已满的状态
urlMap.remove(urlMap.keySet().iterator().next());//先移除头部（最长时间未被访问的数据）
}
urlMap.put(key, value);
} else if (2 == opt) {//get
// 若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
if (urlMap.keySet().contains(key)) {//存在
resultArrayList.add(urlMap.get(key));
} else {//不存在
resultArrayList.add(-1);
}
}
}
int[] result = new int[resultArrayList.size()];
for (int i = 0; i < resultArrayList.size(); i++) {
Integer integer = resultArrayList.get(i);
result[i] = integer;
}
return result;
}
