我的 LRUCache 代码有什么问题

Shu

我尝试解决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;
        }
    }
}
阿伦克2

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

希望能帮助到你!

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章