解析
使用2个Map，一个模拟缓存cache，一个用于记录cache中每条数据的最近访问情况。使用变量time衡量记录访问情况，每次访问/插入，time都加一，插入数据或者访问数据，则更新其最近访问情况为time，在最近访问情况中，time值最小的数据为最近未被访问的数据，每次覆盖最近未被访问的数据，就是覆盖time值虽小的数据。
代码
import java
.util
.*
;
public class Solution {
public int[] LRU
(int[][] operators
, int k
) {
if(operators
.length
==0){
return null
;
}
Map
<Integer,Integer> cache
= new HashMap<>();
Map
<Integer,Integer> readRecord
= new HashMap<>();
int cacheLen
= 0;
List
<Integer> result
= new ArrayList<>();
int time
= 0;
for(int i
=0; i
<operators
.length
; i
++){
time
++;
if(operators
[i
][0]==1){
if(cache
.isEmpty() || cache
.size()<k
){
cache
.put(operators
[i
][1],operators
[i
][2]);
readRecord
.put(operators
[i
][1],time
);
}else {
Integer lastKey
= null
;
Integer minValue
= time
;
for(Integer key
: readRecord
.keySet()){
if(readRecord
.get(key
)<minValue
){
minValue
= readRecord
.get(key
);
lastKey
= key
;
}
}
cache
.remove(lastKey
);
readRecord
.remove(lastKey
);
cache
.put(operators
[i
][1],operators
[i
][2]);
readRecord
.put(operators
[i
][1],time
);
}
}else{
if(cache
.containsKey(operators
[i
][1])){
result
.add(cache
.get(operators
[i
][1]));
readRecord
.put(operators
[i
][1],time
);
}else{
result
.add(-1);
}
}
}
int re
[] = new int[result
.size()];
for(int i
=0; i
<result
.size(); i
++){
re
[i
] = result
.get(i
).intValue();
}
return re
;
}
}
拓展
以上方法在处理小cache时比较有效，但是当cache非常大的时候，每次查询最近访问情况都是极大的资源消耗，所以在实际的计算器操作系统的缓存管理中，则使用循环链表来记录最近访问情况。牛人链接：https://www.iteye.com/blog/gogole-692103
