题解 | #设计LRU缓存结构#

根据队列先进先出进行缓存替换，如果期间有包含key的，就特殊移除key在进队列。key顺序保证后建个字典存值即可。
java，正好使用LinkedList 因为既是链表又实现了队列接口，很好用
public class Solution {
/**
* lru design
* @param operators int整型二维数组 the ops
* @param k int整型 the k
* @return int整型一维数组
*/
public int[] LRU (int[][] operators, int k) {
int resultLength = 0;
for(int i = 0; i < operators.length;i++){
if(operators[i][0] == 2){
resultLength++;
}
}
int [] result = new int[resultLength];
int index = 0;
int value = 0;
LinkedList<integer> objects = new LinkedList<>();
HashMap<Integer,Integer> map = new HashMap<>();
for(int i = 0; i < operators.length;i++){
switch(operators[i][0]){
case 1:
value = operators[i][2];
break;
case 2:
if(objects.contains(operators[i][1])){
result[index] = map.get(operators[i][1]);
}else{
result[index] = -1;
}
value = result[index];
index++;
break;
}
if(value == -1){
continue;
}
if(objects.contains(operators[i][1])){
map.remove(operators[i][1]);
objects.remove(new Integer(operators[i][1]));
}else if(objects.size() == k){
map.remove(objects.poll());
}
objects.add(operators[i][1]);
map.put(operators[i][1],value);
}
return result;
}
}</integer>