DESC:
题目描述
设计LRU缓存结构,该结构在构造时确定大小,假设大小为K,并有如下两个功能
- set(key, value):将记录(key, value)插入该结构
- get(key):返回key对应的value值
[要求]
- set和get方法的时间复杂度为O(1)
- 某个key的set或get操作一旦发生,认为这个key的记录成了最常使用的。
- 当缓存的大小超过K时,移除最不经常使用的记录,即set或get最久远的。
若opt=1,接下来两个整数x, y,表示set(x, y)
若opt=2,接下来一个整数x,表示get(x),若x未出现过或已被移除,则返回-1
对于每个操作2,输出一个答案示例1
输入
[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3返回值
[1,-1]说明
第一次操作后:最常使用的记录为("1", 1) 第二次操作后:最常使用的记录为("2", 2),("1", 1)变为最不常用的 第三次操作后:最常使用的记录为("3", 2),("1", 1)还是最不常用的 第四次操作后:最常用的记录为("1", 1),("2", 2)变为最不常用的 第五次操作后:大小超过了3,所以移除此时最不常使用的记录("2", 2),加入记录("4", 4),并且为最常使用的记录,然后("3", 2)变为最不常使用的记录备注:
1≤K≤N≤1051 \leq K \leq N \leq 10^51≤K≤N≤105 ?2×109≤x,y≤2×109-2 \times 10^9 \leq x,y \leq 2 \times 10^9?2×109≤x,y≤2×10^9
CODE:
JAVA:
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 hereif (operators == null || operators.length == 0) {return new int[0];}List<Integer> resList = new ArrayList();LruCache cache = new LruCache(k);for (int[] opration: operators) {if (opration[0] == 1) {cache.put(opration[1], opration[2]);} else if (opration[0] == 2) {resList.add(cache.get(opration[1]));}}int[] res = new int[resList.size()];int i=0;while (i<resList.size()) {res[i] = resList.get(i);i++;}return res;}class Node {int key, val;Node pre, next;Node(){}Node(int key, int val) {this.key = key;this.val = val;}}class LruCache {private int size=0;private int capacity;private Node head, tail;private Map<Integer, Node> keyMap = new HashMap<>();LruCache (int capacity) {this.capacity = capacity;this.head = new Node();this.tail = new Node();head.next = tail;tail.pre = head;}public int get(int key) {Node node = keyMap.get(key);if (node == null) {return -1;} else {removeNode(node);add2Head(node);return node.val;}}public void put(int key, int val) {Node node = new Node(key, val);if (keyMap.containsKey(key)) {removeNode(node);add2Head(node);} else {add2Head(node);}keyMap.put(key, node);size++;if (size > capacity) {int rkey = removeTail();keyMap.remove(rkey);size--;}}public void add2Head(Node node){node.pre = head;node.next = head.next;head.next.pre = node;head.next = node;}public int removeNode(Node node) {node.pre.next = node.next;node.next.pre = node.pre;return node.key;}public int removeTail() {Node node = tail.pre;removeNode(node);return node.key;}} }
NOTES:
- 使用hashMap和双链表实现
- 注意双链表的插入、删除和去尾操作