菜鸟 贴一个 leetcode LRU Cache -- java代码,并求解疑惑。# JobHunting - 待字闺中
r*7
1 楼
之前面试 遇到过LRU 这道题,面试之前准备过,就直接说了 用hashmap 和
linkedlist。 但是实现起来发现很不好处理 删除命令。 由于是最后一题时间有限就
没在写下去。不过最后一再追问下,知道使用Doublelinkedlist。。。
不过感谢国人面试官,还是给过了。 再次鸣谢下。
然后看到leetcode有这道题(稍微有点不一样)就又做了下,还是问题重重,不得不感
叹自己实力的差距, 不过最后还是通过了,代码如下:
1.由于是菜鸟,代码很丑很啰嗦,希望大神们指点要怎么改进。
2.小弟有一事不明,为啥LRU 还要有(key,value)查询? 现实中,不就只有一个
value吗?然后HashMap 存。 现实中的LRU 每个内存有key
这个值吗?
希望帮忙讲解下LRU。
public class LRUCache {
public HashMap table = new
HashMap();
public DoubleLinkedListNode head;
public DoubleLinkedListNode end;
public int capacity;
public int len;
public LRUCache(int capacity) {
this.capacity = capacity;
len = 0;
}
public int get(int key) {
if (table.containsKey(key)) {
removeNode(table.get(key));
setHead(table.get(key));
return table.get(key).val;
} else {
return -1;
}
}
public void removeNode(DoubleLinkedListNode node){
DoubleLinkedListNode cur = node;
DoubleLinkedListNode pre = cur.pre;
DoubleLinkedListNode post = cur.post;
if(pre!=null){
pre.post = post;
}else{
head = post;
}
if(post != null){
post.pre = pre;
}else{
end = pre;
}
}
public void setHead(DoubleLinkedListNode node){
node.post = head;
node.pre = null;
if(head != null){
head.pre = node;
}
head = node;
if(end == null){
end = node;
}
}
public void set(int key, int value) {
if(table.containsKey(key)){
DoubleLinkedListNode cur = table.get(key);
cur.val = value;
removeNode(cur);
setHead(cur);
}else{
DoubleLinkedListNode cur = new DoubleLinkedListNode(key,value);
if(len < capacity){
setHead(cur);
table.put(key,cur);
len++;
}else{
table.remove(end.key);
end = end.pre;
if(end != null){
end.post = null;
}
setHead(cur);
table.put(key,cur);
}
}
}
public class DoubleLinkedListNode {
public int val;
public int key;
public DoubleLinkedListNode pre;
public DoubleLinkedListNode post;
public DoubleLinkedListNode(int key, int value) {
val = value;
this.key = key;
}
}
}
linkedlist。 但是实现起来发现很不好处理 删除命令。 由于是最后一题时间有限就
没在写下去。不过最后一再追问下,知道使用Doublelinkedlist。。。
不过感谢国人面试官,还是给过了。 再次鸣谢下。
然后看到leetcode有这道题(稍微有点不一样)就又做了下,还是问题重重,不得不感
叹自己实力的差距, 不过最后还是通过了,代码如下:
1.由于是菜鸟,代码很丑很啰嗦,希望大神们指点要怎么改进。
2.小弟有一事不明,为啥LRU 还要有(key,value)查询? 现实中,不就只有一个
value吗?然后HashMap 存
这个值吗?
希望帮忙讲解下LRU。
public class LRUCache {
public HashMap
HashMap
public DoubleLinkedListNode head;
public DoubleLinkedListNode end;
public int capacity;
public int len;
public LRUCache(int capacity) {
this.capacity = capacity;
len = 0;
}
public int get(int key) {
if (table.containsKey(key)) {
removeNode(table.get(key));
setHead(table.get(key));
return table.get(key).val;
} else {
return -1;
}
}
public void removeNode(DoubleLinkedListNode node){
DoubleLinkedListNode cur = node;
DoubleLinkedListNode pre = cur.pre;
DoubleLinkedListNode post = cur.post;
if(pre!=null){
pre.post = post;
}else{
head = post;
}
if(post != null){
post.pre = pre;
}else{
end = pre;
}
}
public void setHead(DoubleLinkedListNode node){
node.post = head;
node.pre = null;
if(head != null){
head.pre = node;
}
head = node;
if(end == null){
end = node;
}
}
public void set(int key, int value) {
if(table.containsKey(key)){
DoubleLinkedListNode cur = table.get(key);
cur.val = value;
removeNode(cur);
setHead(cur);
}else{
DoubleLinkedListNode cur = new DoubleLinkedListNode(key,value);
if(len < capacity){
setHead(cur);
table.put(key,cur);
len++;
}else{
table.remove(end.key);
end = end.pre;
if(end != null){
end.post = null;
}
setHead(cur);
table.put(key,cur);
}
}
}
public class DoubleLinkedListNode {
public int val;
public int key;
public DoubleLinkedListNode pre;
public DoubleLinkedListNode post;
public DoubleLinkedListNode(int key, int value) {
val = value;
this.key = key;
}
}
}