我尝试解决LeetCode 中的一个问题,它要求实现 LRUCache。当我提交代码时,系统告诉我结果是错误的答案。因为TestCase太长,我在我的代码中找不到问题。当我选择“运行代码”来总结我的代码时,它是正确的。
这是我的代码
public class LRUCache {
private int capacity;
private int size;
private HashMap<Integer, Node> cache = new HashMap<>();
private Node tail;
private Node head;
public LRUCache(int capacity) {
this.capacity = capacity;
size = 0;
tail = new Node(-1, -1);
head = new Node(-1, -1);
tail.setPrev(head);
head.setNext(tail);
}
public Integer get(int key) {
Integer value = -1;
Node old = cache.get(key);
if (old != null){
//move to tail
Node node = new Node(key, old.getValue());
removeNode(old);
moveToTail(node);
value = node.getValue();
}
return value;
}
public void put(int key, int value) {
Node n = new Node(key, value);
Node old = cache.get(key);
boolean isExist = old != null;
if (isExist){
removeNode(old);
size--;
}
//move to tail
moveToTail(n);
cache.put(key, n);
size++;
//remove node if size upper than capacity
while (capacity < size){
Node rm = head.getNext();
cache.remove(rm.getKey());
removeNode(rm);
size--;
}
}
private void removeNode(Node node){
if (node.getPrev() != head){
node.getPrev().setNext(node.getNext());
node.getNext().setPrev(node.getPrev());
}else {
head.setNext(node.getNext());
node.getNext().setPrev(head);
}
node = null;
}
private void moveToTail(Node node){
node.setPrev(tail.getPrev());
tail.getPrev().setNext(node);
tail.setPrev(node);
node.setNext(tail);
}
private class Node{
private int key;
private int value;
private Node prev;
private Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
public int getKey() {
return key;
}
public int getValue() {
return value;
}
public Node getPrev() {
return prev;
}
public void setPrev(Node prev) {
this.prev = prev;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
}
我猜你的 get 和 put 方法有问题。每次创建新节点时。理想情况下,它应该是跨 DLL 移动的同一节点。此外,节点应该有一个用于更新的 setValue() 方法。
以下更新应该有效。
public Integer get(int key) {
Integer value = -1;
Node old = cache.get(key);
if (old != null){
//move to tail
/////Node node = new Node(key, old.getValue());
removeNode(old);
moveToTail(old);
value = old.getValue();
}
return value;
}
public void put(int key, int value) {
Node n = null;
n = cache.get(key);
if (n != null){
//Update the value of node and move
n.setValue(value);
removeNode(n);
size--;
}
else {
n = new Node(key, value);
}
//move to tail
moveToTail(n);
cache.put(key, n);
size++;
//remove node if size upper than capacity
while (capacity < size){
Node rm = head.getNext();
cache.remove(rm.getKey());
removeNode(rm);
size--;
}
}
希望能帮助到你!
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句