注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
我前几天看见面经里有提到环形LRU的设计,就自己实现了一下,结果过不了leetcode的test,看来看去没看出问题,求各路大神指教。
package algo_leetcode;
import java.util.HashMap;
class DoubleLinkedListNode{
DoubleLinkedListNode pre, next;
int val;
int key;
public DoubleLinkedListNode( int key, int val ){
this.val = val;
this.key = key;
}
}
public class LRUCache {
DoubleLinkedListNode cut = null;
int cap;
HashMap< Integer , DoubleLinkedListNode > mp = new HashMap< Integer , DoubleLinkedListNode >();
public LRUCache(int capacity) {
this.cap = capacity;
}
public int get(int key) {
if ( mp.get( key ) == null ) {
return -1;
} else if ( mp.get( key ) != cut ) {
deleteNode( mp.get( key ) );
setHead( mp.get( key ) );
}
return cut.val;
}
public void set(int key, int value) {
if ( mp.get( key ) != null ) {
mp.get( key ).val = value;
deleteNode( mp.get( key ) );
setHead( mp.get( key ) );
} else {
DoubleLinkedListNode cur = new DoubleLinkedListNode(key , value);
if ( mp.size() == 0 ) {
cur.pre = cur;
cur.next = cur;
cut = cur;
} else if( mp.size() < cap ) {
setHead(cur);
} else {
mp.remove( cut.pre.key );
deleteNode( cut.pre );
setHead( cur );
}
mp.put( key , cur );
}
}
private void setHead(DoubleLinkedListNode cur){
DoubleLinkedListNode lst = cut.pre;
cur.next = cut;
cut.pre = cur;
cur.pre = lst;
lst.next = cur;
cut = cur;
}
private void deleteNode( DoubleLinkedListNode cur ){
DoubleLinkedListNode pre = cur.pre;
DoubleLinkedListNode nxt = cur.next;
if ( pre != null) {
pre.next = nxt;
}
if ( nxt != null ) {
nxt.pre = pre;
}
}
} |