题解 | #设计LRU缓存结构#
设计LRU缓存结构
http://www.nowcoder.com/practice/e3769a5f49894d49b871c09cadd13a61
使用双向链表 HashMap实现O(1)
import java.util.*; public class Solution { Map<Integer, Integer> map = new HashMap<>(); Deque<Integer> list = new LinkedList<>(); int k; /** * 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> res = new ArrayList<>(); this.k = k; for (int[] op : operators) { if (op[0] == 1) { set(op[1], op[2]); } else { res.add(get(op[1])); } } return res.stream().mapToInt(Integer::valueOf).toArray(); } private void set (int key, int value) { if (map.containsKey(key)) { list.remove(key); } list.offer(key); if (map.size() == k) { Integer rm = list.poll(); map.remove(rm); } map.put(key, value); } public int get (int key) { if (map.containsKey(key)) { list.remove(key); list.offer(key); return map.get(key); } return -1; } }