题目要求
设计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，输出一个答案
思路
参考自《程序员代码面试指南》：
- 使用一个双向链表保存节点的值。双向链表的头部为优先级最低的位置，双向链表的尾部为优先级最高的位置。
- 设置keyNodeMap和nodeKeyMap完成键到节点的映射以及节点到键的映射，保证set和get的时间复杂度都为O(1)。
- 节点只保存值，不保存键。
- set操作：先通过keyNodeMap检查双向链表中有没有当前键，如果有，则修改node的值并将node移到链表尾部。如果没有，则在链表尾部插入该节点。（每个插入操作中应检查插入后的链表长度是否大于k，如果是，则移除链表头部的节点）。
- get操作：通过keyNodeMap检查双向链表中是否有当前的键，如果有，返回对应node的value，如果没有，返回-1。
- 为什么使用双向链表而不是单向链表：可以方便的获得链表头部节点和尾部节点，保证时间复杂度为O(1)。
代码实现
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
if(operators == null || operators.length == 0){
return null;
}
ArrayList <Integer> list = new ArrayList<>();
LRULinkedList LRUList = new LRULinkedList(k);
for(int i = 0 ; i<operators.length ; i++){
if(operators[i][0] == 1){
LRUList.set(operators[i][1], operators[i][2]);
}else if(operators[i][0] == 2){
//如果LRUList中不存在当前元素，则返回-1.
list.add(LRUList.get(operators[i][1]));
}
}
int [] arr = new int[list.size()];
for(int i = 0 ; i<arr.length ; i++){
arr[i] = list.get(i);
}
return arr;
}
class Node{
public int value;
public Node next,pre;
Node(int value){
this.value = value;
}
}
class LRULinkedList{
//双向链表
//头部节点优先级最低，尾部节点优先级最高
private Node head;
private Node tail;
int size;//最大容量
//将key单独存储，而不是存在node中
HashMap<Integer,Node> keyNodeMap = new HashMap<>();
HashMap<Node, Integer> nodeKeyMap = new HashMap<>();
LRULinkedList(int k){
size = k;//写成int size = k；导致出错
}
//先在链表中查找该元素，如果找到，则将该元素移到链表尾部
//如果查找不到，则在链表尾部插入该元素，此时需要检查链表长度是否大于等于size,如果是，则移出链表头部的元素
public void set(int key, int value){
if(keyNodeMap.containsKey(key)){
Node node = keyNodeMap.get(key);
//将node移到链表尾部
moveToLast(node);
}else{
Node node = new Node(value);
insertToLast(node);
keyNodeMap.put(key, node);
nodeKeyMap.put(node, key);
if(keyNodeMap.size() > size){
Node oldHead = removeHead();
int oldHeadKey = nodeKeyMap.get(oldHead);
nodeKeyMap.remove(oldHead);
keyNodeMap.remove(oldHeadKey);
}
}
}
//检查当前的key是否在链表中，
//如果在，就返回该key对应的node的value，然后将该节点移到链表尾部
//如果不在，直接返回-1。
public int get(int key){
if(keyNodeMap.containsKey(key)){
int value = keyNodeMap.get(key).value;
moveToLast(keyNodeMap.get(key));
return value;
}else{
return -1;
}
}
private void moveToLast(Node node){
//首先查找到该节点
//将该节点在原位置删除
//将节点加入新的位置
if(node == head){
node.next.pre = null;
head = node.next;
}else if(node == tail){
return;
}else{
//在原位置删除
node.pre.next = node.next;
node.next.pre = node.pre;
}
//加入尾部
tail.next = node;
node.pre = tail;
node.next = null;
tail = node;
}
private void insertToLast(Node node){
if(head == null && tail == null){
node.pre = null;
node.next = null;
head = node;
tail = node;
return;
}
tail.next = node;
node.pre = tail;
node.next = null;
tail = node;
}
private Node removeHead(){
//只有一个节点
if(head == tail){
Node node = head;
head = null;
tail = null;
return node;
}
Node node = head;
head.next.pre = null;
head = head.next;
return node;
}
}
}