f**********3
发帖数: 295 | 1 希望用java.util的HashMap和LinkedList，搞了两天没搞出来，太弱了。自己写的
Linked List没有问题，但是这个自带的LinkedList没找到给定node reference, O(1)
删除的方法，估计要用ListIterator? 然后这些ListIterator存在HashMap里？ 不然会
超时。
C++反正本来也是自己写LinkedList，没有问题，但是这个用standard java
LinkedList就是搞不定啊... |
l*n
发帖数: 529 | 2 为啥非要用library LinkedList？自己写一个DoubleLinkedList很简单啊。
【在 f**********3 的大作中提到】
: 希望用java.util的HashMap和LinkedList，搞了两天没搞出来，太弱了。自己写的
: Linked List没有问题，但是这个自带的LinkedList没找到给定node reference, O(1)
: 删除的方法，估计要用ListIterator? 然后这些ListIterator存在HashMap里？ 不然会
: 超时。
: C++反正本来也是自己写LinkedList，没有问题，但是这个用standard java
: LinkedList就是搞不定啊...
|
m**********4
发帖数: 774 | 3 自己写个DOUBLY LINKEDLIST吧，自己写java能通过的。
【在 f**********3 的大作中提到】
: 希望用java.util的HashMap和LinkedList，搞了两天没搞出来，太弱了。自己写的
: Linked List没有问题，但是这个自带的LinkedList没找到给定node reference, O(1)
: 删除的方法，估计要用ListIterator? 然后这些ListIterator存在HashMap里？ 不然会
: 超时。
: C++反正本来也是自己写LinkedList，没有问题，但是这个用standard java
: LinkedList就是搞不定啊...
|
f**********3
发帖数: 295 | 4 从我的经验看来，面试官经常问为什么不用standard，而且这样给人语言不熟练的感觉
，所以想知道这个standard的到底怎么写...
【在 m**********4 的大作中提到】
: 自己写个DOUBLY LINKEDLIST吧，自己写java能通过的。
|
l*n
发帖数: 529 | 5 答案是can't。library没有提供O(1)删除节点的办法。
【在 f**********3 的大作中提到】
: 从我的经验看来，面试官经常问为什么不用standard，而且这样给人语言不熟练的感觉
: ，所以想知道这个standard的到底怎么写...
|
f**********3
发帖数: 295 | 6 问题是真的没有还是只是我不知道，可能某种Iterator可以？
【在 l*n 的大作中提到】
: 答案是can't。library没有提供O(1)删除节点的办法。
|
l*n
发帖数: 529 | 7 但凡涉及iterator就不是O(1)了。
http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.h
删除方法就那么几个，挨个排除就知道了。
【在 f**********3 的大作中提到】
: 问题是真的没有还是只是我不知道，可能某种Iterator可以？
|
r*********r
发帖数: 53 | 8 其实删除倒不是问题。 用 ListIterator就可以。http://docs.oracle.com/javase/7/docs/api/java/util/ListIterator.html
ListIterator 可以向前也可以向后，可增加可以删除。
但是问题是每次一改变linkedlist后，原来的ListIterator就不能用了，如果用的话会
抛出concurrency的异常，所以我们没办法用把它放到hashmap里，因为一旦linkedlist
里增加或者删除了某个结点，在这次增加或者删除之前存在hashmap里的其它iterator
就不能用了。
我还没有找到其它更好的方法。 java里的iterator不如c++里的iterator强大。
如果有大牛知道怎么作的话，求教。
【在 l*n 的大作中提到】
: 但凡涉及iterator就不是O(1)了。
: http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.h
: 删除方法就那么几个，挨个排除就知道了。
|
l*n
发帖数: 529 | 9 我的意思是删除某个指定元素不能靠iterator。删除当前指向的当然OK啦。
linkedlist
iterator
【在 r*********r 的大作中提到】
: 其实删除倒不是问题。 用 ListIterator就可以。http://docs.oracle.com/javase/7/docs/api/java/util/ListIterator.html
: ListIterator 可以向前也可以向后，可增加可以删除。
: 但是问题是每次一改变linkedlist后，原来的ListIterator就不能用了，如果用的话会
: 抛出concurrency的异常，所以我们没办法用把它放到hashmap里，因为一旦linkedlist
: 里增加或者删除了某个结点，在这次增加或者删除之前存在hashmap里的其它iterator
: 就不能用了。
: 我还没有找到其它更好的方法。 java里的iterator不如c++里的iterator强大。
: 如果有大牛知道怎么作的话，求教。
|
r*********r
发帖数: 53 | 10 恩，对的。我想的办法是用map, 但是这样一旦改变list的结构，
就不能用了。真蛋疼。
【在 l*n 的大作中提到】
: 我的意思是删除某个指定元素不能靠iterator。删除当前指向的当然OK啦。
:
: linkedlist
: iterator
|
|
|
w*******i
发帖数: 186 | 11 楼主早上发过问这道题的贴，没想到这会儿有发了后续问题了。钻研精神先赞一个！
按照rookiecode的结论，看来Iterator（包括ListIterator）这种用来指向对象逻辑地
址的类貌似不管用啊。可是Java偏偏又是屏蔽物理地址的。哎，要怪就怪Java没有提供
C++的list中类似splice的方法吧。。。
话说回来，要是非要展现自己对library的熟练程度，楼主可以考虑使用LinkedHashMap
，这个类专门用于实现LRU的思想。 |
f**********3
发帖数: 295 | 12 大牛，LinkedHashMap就已经搞定了，不用写了... 综合各大牛的意见，貌似还是自己
写个doubly linked list比较靠谱。貌似问题是java的LinkedList把node藏的太深了。
LinkedHashMap
【在 w*******i 的大作中提到】
: 楼主早上发过问这道题的贴，没想到这会儿有发了后续问题了。钻研精神先赞一个！
: 按照rookiecode的结论，看来Iterator（包括ListIterator）这种用来指向对象逻辑地
: 址的类貌似不管用啊。可是Java偏偏又是屏蔽物理地址的。哎，要怪就怪Java没有提供
: C++的list中类似splice的方法吧。。。
: 话说回来，要是非要展现自己对library的熟练程度，楼主可以考虑使用LinkedHashMap
: ，这个类专门用于实现LRU的思想。
|
x*******8
发帖数: 145 | 13 面试被问道，直接用LinkedHashMap貌似会被鄙视，之前我试过，让我自己另外写。 |
b********6
发帖数: 97 | 14 贴个我刚通过的解法 608ms
public class LRUCache {
static public class Pair {
int key;
int val;
Pair before;
Pair next;
public Pair(int k, int v){
key = k;
val = v;
before = null;
next = null;
}
}
//private LinkedList< Pair > item_list ;
//private ArrayDeque item_list;
private Pair head;
private Pair tail;
private HashMap item_map;
private int cap;
private int size;
public LRUCache(int capacity) {
head = new Pair(-1,-1);
tail = new Pair(-1,-1);
head.next = tail;
tail.before = head;
item_map = new HashMap();
cap = capacity;
size = 0;
}
private void clean(){
while(size>cap){
Pair last_it = tail.before;
remove(last_it);
item_map.remove(last_it.key);
size--;
}
}
public int get(int key) {
//assert(exist(key));
if (!item_map.containsKey(key)) return -1;
Pair it = item_map.get(key);
if (it != head.next){
remove(it);
addFirst(it);
}
return it.val;
}
public void set(int key, int value) {
if(item_map.containsKey(key)){
Pair it = item_map.get(key);
//item_list.remove(it);
remove(it);
item_map.remove(key);
size--;
}
Pair newNode = new Pair(key,value);
addFirst(newNode);
item_map.put(key, head.next);
size++;
clean();
}
private void addFirst(Pair node){
node.next = head.next;
head.next.before = node;
head.next = node;
node.before = head;
}
private void remove(Pair node){
node.before.next = node.next;
node.next.before = node.before;
}
}
【在 f**********3 的大作中提到】
: 希望用java.util的HashMap和LinkedList，搞了两天没搞出来，太弱了。自己写的
: Linked List没有问题，但是这个自带的LinkedList没找到给定node reference, O(1)
: 删除的方法，估计要用ListIterator? 然后这些ListIterator存在HashMap里？ 不然会
: 超时。
: C++反正本来也是自己写LinkedList，没有问题，但是这个用standard java
: LinkedList就是搞不定啊...
|
z**********r
发帖数: 86 | 15 发一个我的实现吧，已经通过了leetcode：
https://github.com/zhangtemplar/LeetCode/blob/second-trial/src/Solution/
LRUCache.java
基本思想就是：用double linked list to store the key, we will keep the
recently used key in the tail and thus least recently used key in the head;
we use hashmap to store pair.
Each time we access a key, we move it to the tail of list. If the list is
full, we remove its head. To quick access the list node, we use a hashmap to
map key to the node。
网上说可以用java的linkedhashmap，我还没有去想。 |
d****n
发帖数: 233 | 16 Share my solution:
class DLLNode {
public int value;
public int key;
public DLLNode left;
public DLLNode right;
public DLLNode(int k, int val)
{
key = k;
value = val;
left = this;
right = this;
}
public void detach()
{
right.left = left;
left.right = right;
}
public void addLeft(DLLNode node)
{
left.right = node;
node.left = left;
node.right = this;
left = node;
}
}
public class LRUCache {
private int m_cap = 0;
private DLLNode pivot = new DLLNode(0,0);
private HashMap m_map;
public LRUCache(int capacity) {
m_cap = capacity;
m_map = new HashMap();
}
public int get(int key) {
if (m_map.containsKey(key)) {
DLLNode r = m_map.get(key);
r.detach();
pivot.addLeft(r);
return r.value;
}
return -1;
}
public void set(int key, int value) {
if (m_map.containsKey(key)) {
DLLNode r = m_map.get(key);
r.detach();
m_map.remove(r.key);
}
if (m_map.size() >= m_cap) {
DLLNode r = pivot.right;
m_map.remove(r.key);
r.detach();
}
DLLNode dn = new DLLNode(key, value);
m_map.put(key, dn);
pivot.addLeft(dn);
}
}
;
to
【在 z**********r 的大作中提到】
: 发一个我的实现吧，已经通过了leetcode：
: https://github.com/zhangtemplar/LeetCode/blob/second-trial/src/Solution/
: LRUCache.java
: 基本思想就是：用double linked list to store the key, we will keep the
: recently used key in the tail and thus least recently used key in the head;
: we use hashmap to store pair.
: Each time we access a key, we move it to the tail of list. If the list is
: full, we remove its head. To quick access the list node, we use a hashmap to
: map key to the node。
: 网上说可以用java的linkedhashmap，我还没有去想。
|
