题解 | #设计LRU缓存结构#
设计LRU缓存结构
http://www.nowcoder.com/practice/e3769a5f49894d49b871c09cadd13a61
这道题总体来说比较复杂。首先说一下本题主要用的思想是hashmap+双向链表。
为什么要使用hashmap，因为这样在根据key取值的时候很快，如果只有一个双向链表，那么需要遍历去找值，很麻烦。
为什么要使用双向链表，因为会不断涉及到元素的插入删除，如果单链表删除的话很麻烦。
首先就是定义一个数据结构:
static class Node{ int k,v; Node pre,next; public Node(int k,int v) { this.k = k; this.v = v; } }然后遍历输入的数组。
int num = 0;
int count = 0;
for(int i=0;i<operators.length;i++){
if(operators[i][0]==2){
num++;
}
}
int[] ret = new int[num];
HashMap<Integer,Node> map = new HashMap<>();
for(int i=0;i<operators.length;i++){
if(operators[i][0]==1){
put(map,operators[i][1],operators[i][2],k);
}else{
ret[count++]=get(map,operators[i][1]);
}
}
return ret;
那么关键就在于插入和获取操作。
插入操作需要注意一点的是覆盖问题，如果这个元素已经了有了，那么从map中取出来，将其value值改一下即可。并且要把这个节点移动到结尾。如果这个节点本身就在结尾那么不用移动。
正常的插入就是
如下代码:
public static void put(HashMap<Integer,Node> map,int k,int v,int size){
//覆盖没有考虑
Node p = new Node(k,v);
if(map.containsKey(k)){
Node node = map.get(k);
node.v = v;
map.put(k,node);
//把这个节点移动到尾部
if(node.next!=null){
pre.next = node;
node.pre = pre;
pre = node;
head = head.next;
head.pre=null;
node.next = null;
}
return;
}
map.put(k,p);
if(n==0){
head = p;
}
n++;
p.next = null;
p.pre = pre;
if(pre!=null){
pre.next = p;
}
pre = p;
if(map.size()>size){
map.remove(head.k);
head = head.next;
head.pre = null;
}
}
如果这个元素就在尾部，那么不需要移动。
如果这个元素不在尾部，那么需要改变链表结构。
如果这个元素不在尾部，那么需要改变链表结构。
如果map根本就没这个元素那么直接返回-1
如果这个元素在头部那么也需要做特殊处理
public static int get(HashMap<Integer,Node> map,int k){
if(!map.containsKey(k)){
return -1;
}
Node node = map.get(k);
if(node.pre==null){
pre.next = node;
node.pre = pre;
head = node.next;
head.pre = null;
node.next=null;
pre = node;
}else if(node.next==null){
//这个节点本身就在尾部，不需要移动
System.out.println("1");
}else{
node.pre.next = node.next;
node.next.pre = node.pre;
pre.next = node;
node.next = null;
node.pre = pre;
pre = node;
}
return node.v;
}
腾讯二面453人在聊