Quel est le problème avec mon code LRUCache

Question

J'essaie de résoudre une question en LeetCode, il est demandé d'implémenter un LRUCache. Et quand j'ai soumis mon code, le Système m'a dit que le résultat est Mauvaise Réponse. Parce que le TestCase est trop long, je ne trouve pas le problème dans mon code. Et quand je choisis "Run code" pour sumbiter mon code, c'est correct.

Voici mon code

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

Je crois qu'il ya problème dans votre get et mettre des méthodes. Chaque fois que vous créez de nouveaux nœuds. Idéalement, il devrait être le même nœud déplacé à travers la DLL. En outre, le noeud doit avoir une méthode setValue() pour les mises à jour.

La mise à jour suivante devrait fonctionner.

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

Espérons que ça aide!