我的LRUCache代码有什么问题

Question

我试图解决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; 
     } 
    } 
} 

Answer 1

我想有一个问题，你的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--; 
    } 
} 

希望它有帮助！