题解 | #设计LRU缓存结构#
设计LRU缓存结构
http://www.nowcoder.com/practice/e3769a5f49894d49b871c09cadd13a61
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 ArrayList<Integer> list = new ArrayList<>(); LRUCache cache = new LRUCache(k); for(int[] next : operators){ if(next[0] == 1){ //set cache.set(next[1],next[2]); } else { //get int value = cache.get(next[1]); list.add(value); } } int[] result = new int[list.size()]; for(int i = 0;i< list.size();i++){ result[i] = list.get(i); } return result; }
public class LRUCache{ private int size = 0; private LinkedHashMap<Integer,Integer> map = new LinkedHashMap<>(); public LRUCache(int size){ this.size = size; } public void set(int key,int value){ if(map.containsKey(key)){ //设置为最近使用 删除 再添加即可 map.remove(key); } //添加之前判断是否超过大小 if(map.size() == size){ //删除头部元素 int headKey = map.keySet().iterator().next(); map.remove(headKey); } map.put(key,value); } public int get(int key){ if(map.containsKey(key)){ //返回之前 设置为最近使用 删除重新添加即可 int value = map.get(key); map.remove(key); map.put(key,value); return value; } else { return -1; } } }
}