求leetcode LRU Java 解法 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

求leetcode LRU Java 解法

求leetcode LRU Java 解法# JobHunting - 待字闺中

f*32013-11-12 08:11

1 楼

希望用java.util的HashMap和LinkedList，搞了两天没搞出来，太弱了。自己写的
Linked List没有问题，但是这个自带的LinkedList没找到给定node reference, O(1)
删除的方法，估计要用ListIterator? 然后这些ListIterator存在HashMap里？不然会
超时。
C++反正本来也是自己写LinkedList，没有问题，但是这个用standard java
LinkedList就是搞不定啊...

l*n2013-11-12 08:11

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*42013-11-12 08:11

3 楼

自己写个DOUBLY LINKEDLIST吧，自己写java能通过的。

【在 f**********3 的大作中提到】

f*32013-11-12 08:11

4 楼

从我的经验看来，面试官经常问为什么不用standard，而且这样给人语言不熟练的感觉
，所以想知道这个standard的到底怎么写...

【在 m**********4 的大作中提到】

: 自己写个DOUBLY LINKEDLIST吧，自己写java能通过的。

l*n2013-11-12 08:11

5 楼

答案是can't。library没有提供O(1)删除节点的办法。

【在 f**********3 的大作中提到】

: 从我的经验看来，面试官经常问为什么不用standard，而且这样给人语言不熟练的感觉
: ，所以想知道这个standard的到底怎么写...

f*32013-11-12 08:11

6 楼

问题是真的没有还是只是我不知道，可能某种Iterator可以？

【在 l*n 的大作中提到】

: 答案是can't。library没有提供O(1)删除节点的办法。

l*n2013-11-12 08:11

7 楼

但凡涉及iterator就不是O(1)了。
http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.h
删除方法就那么几个，挨个排除就知道了。

【在 f**********3 的大作中提到】

: 问题是真的没有还是只是我不知道，可能某种Iterator可以？

r*r2013-11-12 08:11

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*n2013-11-12 08:11

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*r2013-11-12 08:11

10 楼

恩，对的。我想的办法是用map, 但是这样一旦改变list的结构，
就不能用了。真蛋疼。

【在 l*n 的大作中提到】

: 我的意思是删除某个指定元素不能靠iterator。删除当前指向的当然OK啦。
:
: linkedlist
: iterator

w*i2013-11-12 08:11

11 楼

楼主早上发过问这道题的贴，没想到这会儿有发了后续问题了。钻研精神先赞一个！
按照rookiecode的结论，看来Iterator（包括ListIterator）这种用来指向对象逻辑地
址的类貌似不管用啊。可是Java偏偏又是屏蔽物理地址的。哎，要怪就怪Java没有提供
C++的list中类似splice的方法吧。。。
话说回来，要是非要展现自己对library的熟练程度，楼主可以考虑使用LinkedHashMap
，这个类专门用于实现LRU的思想。

f*32013-11-12 08:11

12 楼

大牛，LinkedHashMap就已经搞定了，不用写了... 综合各大牛的意见，貌似还是自己
写个doubly linked list比较靠谱。貌似问题是java的LinkedList把node藏的太深了。

LinkedHashMap

【在 w*******i 的大作中提到】

: 楼主早上发过问这道题的贴，没想到这会儿有发了后续问题了。钻研精神先赞一个！
: 按照rookiecode的结论，看来Iterator（包括ListIterator）这种用来指向对象逻辑地
: 址的类貌似不管用啊。可是Java偏偏又是屏蔽物理地址的。哎，要怪就怪Java没有提供
: C++的list中类似splice的方法吧。。。
: 话说回来，要是非要展现自己对library的熟练程度，楼主可以考虑使用LinkedHashMap
: ，这个类专门用于实现LRU的思想。

x*82013-11-12 08:11

13 楼

面试被问道，直接用LinkedHashMap貌似会被鄙视，之前我试过，让我自己另外写。

b*62013-11-12 08:11

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 的大作中提到】

z*r2013-11-12 08:11

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*n2013-11-12 08:11

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，我还没有去想。