r********7
发帖数: 102 | 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;
}
}
} |
l*n
发帖数: 529 | 2 这里可以用两个不算做数据的dummy head、tail node，否则考虑头尾的conner case很
麻烦。
key
【在 r********7 的大作中提到】
: 之前面试 遇到过LRU 这道题，面试之前准备过，就直接说了 用hashmap 和
: linkedlist。 但是实现起来发现很不好处理 删除命令。 由于是最后一题时间有限就
: 没在写下去。不过最后一再追问下，知道使用Doublelinkedlist。。。
: 不过感谢国人面试官，还是给过了。 再次鸣谢下。
: 然后看到leetcode有这道题（稍微有点不一样）就又做了下，还是问题重重，不得不感
: 叹自己实力的差距, 不过最后还是通过了，代码如下：
: 1.由于是菜鸟，代码很丑很啰嗦，希望大神们指点要怎么改进。
: 2.小弟有一事不明，为啥LRU 还要有（key,value）查询？ 现实中，不就只有一个
: value吗？然后HashMap 存。 现实中的LRU 每个内存有key
: 这个值吗？
|
r********7
发帖数: 102 | 3 嘻嘻，没看懂。。 啥叫dummy head， tail 啊？ 怎么实现呢？
每次都考虑头尾，确实很麻烦，弄得头大。。
【在 l*n 的大作中提到】
: 这里可以用两个不算做数据的dummy head、tail node，否则考虑头尾的conner case很
: 麻烦。
:
: key
|
z****e
发帖数: 54598 | 4 就是safe guard
在head前面搞一个node，然后node的指针指向head
同理，在tail后面搞一个node
这样当你删除head和tail的时候，就少折腾很多
指针题这种操作常见
【在 r********7 的大作中提到】
: 嘻嘻，没看懂。。 啥叫dummy head， tail 啊？ 怎么实现呢？
: 每次都考虑头尾，确实很麻烦，弄得头大。。
|
z****e
发帖数: 54598 | 5 内部类看得我很痛苦
好久没见到内部类了
把内部类放到类外
单独一个
class DoubleLinkedListNode{...
去掉public，反正你也不会在其它地方用到
这样就可以干掉LRUCache.这个前缀 |
w********s
发帖数: 214 | 6 代码太多啦，不需要写doublelinkedlist 这个类，Java自带的linkedlist本身就是
doubly linked list.
那个key是用来取址的。内存当然要有page address + offset才能retrieve content啦。
每次你refresh key的时候先 remove the key from the linkedlist (keys) then add
it back.
几行应该就可以吧 |
w********s
发帖数: 214 | 7 感觉那个题目描述不是很清楚，我在网上看到一个CPP版本的通过版，貌似那个题目没
有考虑 hashtable的collision，本来也对，这个是cache给了明确地址也就没有
collision了，其实用linkedlist maintain当前的keys。每次get或者insert的时候刷
新keys 同时更新hashtable 就应该可以了吧？如果我说的不对，还希望有明白的大牛
给指点一下。 |
r*******n
发帖数: 3020 | 8 用circle doubly-linked list 用一个dummy head就行了
【在 l*n 的大作中提到】
: 这里可以用两个不算做数据的dummy head、tail node，否则考虑头尾的conner case很
: 麻烦。
:
: key
|
g****r
发帖数: 74 | 9 我是用linkedHashMap 做的 是不是有点偷懒啊 |
c********w
发帖数: 308 | 10 这题要是用java linkedlist,remove无法constant吧。 用linkedhashmap到是可以了。
但对于准备面试就没意义了。看来还是要自己定义一个双向链表。 |
j*********6
发帖数: 407 | 11 想问一下 用java 的 linkedlist 是不是也要定义一个 node 这个class 用来存 <
key, value> pair ?
还有这个linkedlist的remove是constant的吧？ 就是因为加了 hashmap所以变成
constant了？ |
l*********h
发帖数: 15 | 12 贴一个我的
public class LRUCache {
private Map map;
private Entry head;
private int size;
private final int CAPACITY;
private class Entry {
private int key;
private int val;
private Entry prev, next;
private Entry(){}
public Entry (int key, int val) {
this.key = key;
this.val = val;
}
}
public LRUCache(int capacity) {
map = new HashMap();
head = new Entry();
head.next = head;
head.prev = head;
CAPACITY = capacity;
size = 0;
}
public int get(int key) {
Entry node = map.get(key);
if (node == null) return -1;
detach(node);
addFirst(node);
return node.val;
}
public void set(int key, int value) {
Entry node = map.get(key);
if (node != null) {
detach(node);
node.val = value;
addFirst(node);
} else {
if (size == CAPACITY) {
removeLast();
size--;
}
node = new Entry(key, value);
addFirst(node);
size++;
map.put(key, node);
}
}
public void detach(Entry node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
public void addFirst(Entry node) {
node.prev = head;
node.next = head.next;
head.next = node;
node.next.prev = node;
}
public void removeLast() {
Entry node = head.prev;
head.prev = node.prev;
node.prev.next = head;
node.prev = null;
node.next = null;
map.remove(node.key);
}
} |
b*****6
发帖数: 179 | 13 这个题单向列表也可以做，不过代码复杂很多。两个办法
1.hashmap里存的永远是前一个node的指针，或者
2.每次把下一个node的数据挪到当前node，然后删除下一个node。 |
b**m
发帖数: 1466 | 14 内部类在这里没什么问题，但可以用static 的。
LRUCache. 是不必要的。
len 是不是多余的map#size可以得到
用dummy 节点代码应该会更容易写对。
【在 z****e 的大作中提到】
: 内部类看得我很痛苦
: 好久没见到内部类了
: 把内部类放到类外
: 单独一个
: class DoubleLinkedListNode{...
: 去掉public，反正你也不会在其它地方用到
: 这样就可以干掉LRUCache.这个前缀
|
