我的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--; 
    } 
} 

希望它有幫助！