题解 | #设计LRU缓存结构#
设计LRU缓存结构
http://www.nowcoder.com/practice/e3769a5f49894d49b871c09cadd13a61
定义一个LinkedHashMap来存取当前缓存里的key-value，遍历数组，如果第一位为1，且之后一位的key在map中没有，就把它加入到map当中，当key-value数量大于最大值k时移除第一个位置的key-value；
如果已经存在，将存在的key-value移除，添加当前key-value；如果第一位为2，为get操作，get找到了key就将其值加入定义的列表中，反之将-1加入列表中，之后将当前key-value移到最后进行下一步。数组遍历完，将
list里的值全部赋给结果数组返回
import java.util.*;
public class Solution {
/**
* lru design
* @param operators int整型二维数组 the ops
* @param k int整型 the k
* @return int整型一维数组
*/
public int[] LRU (int[][] operators, int k) {
// write code here
LinkedHashMap<Integer,Integer> map=new LinkedHashMap<>();
List<Integer> list=new ArrayList<>();
for(int[] op:operators){
if(op[0]==1){
if(!map.containsKey(op[1])){
if(map.size()==k)
map.remove(map.keySet().iterator().next());
map.put(op[1],op[2]);
}else{
map.remove(op[1]);
map.put(op[1],op[2]);
}
}else if(op[0]==2){
if(map.containsKey(op[1])){
int val=map.get(op[1]);
list.add(val);
map.remove(op[1]);
map.put(op[1],val);
}
else{
list.add(-1);
}
}
}
int[] res=new int[list.size()];
for(int i=0;i<list.size();i++){
res[i]=list.get(i);
}
return res;
}
} 