java - 我的 LRUCache 代码有什么问题

Question

我尝试解决 LeetCode 中的问题，要求实现一个LRUCache。当我提交代码时，系统告诉我结果是错误答案。 由于测试用例太长，我在代码中找不到问题。当我选择“运行代码”来提交我的代码时，它是正确的。

这是我的代码

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

希望对你有帮助!