내 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

나는 문제가 당신의 취득으로이 추측과 방법을 넣어이다. 새 노드를 만들 때마다. 이상적으로 그것은 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--; 
    } 
} 

희망 하시겠습니까?