Estoy haciendo una pregunta de leetcode: sumar dos números

Uno de los testCases no está pasando y estoy al final de mi ingenio en cuanto a por qué se pierde el último valor de mi programa. Aquí está el código:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //have to use bit addition here
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }

        int b1=0, b2=0, resBit = 0, carryBit=0;
        ListNode res = new ListNode(-1);
        ListNode dummy = res;

        while(l1!=null && l2!=null){
            resBit = l1.val+l2.val+carryBit;
            if(resBit >9){
                carryBit=1;
                resBit=resBit%10;
            }
            else{
                carryBit=0;
            }
            dummy.next = new ListNode(resBit);
            l1=l1.next;
            l2=l2.next;
            dummy=dummy.next;
        }

        //add any remaining numbers to our result

        if(l1!=null){
            System.out.println(l1.val);
            if(carryBit!=0){
                resBit = l1.val+carryBit;
                if(resBit >9){
                    carryBit=1;
                    resBit=resBit%10;
                }
                else{
                    carryBit=0;
                }
                dummy.next = new ListNode(resBit);
            }
            else{

                dummy.next = new ListNode(l1.val);
            }
            l1=l1.next;
            System.out.println(l1.val);
            dummy=dummy.next;
        }

        if(l2!=null){
            if(carryBit!=0){
                resBit = l2.val+carryBit;
                if(resBit >9){
                    carryBit=1;
                    resBit=resBit%10;
                }
                else{
                    carryBit=0;
                }
                dummy.next = new ListNode(resBit);
            }
            else{
                dummy.next = new ListNode(l2.val);
            }
            l2=l2.next;
            dummy=dummy.next;
        }

        if(carryBit!=0){
            dummy.next = new ListNode(carryBit);
        }


        //remove the -1 used to create the LL initially
        res = res.next;

        return res;
    }
} 

Aquí están los detalles del caso de prueba fallido:

Tiempo de ejecución de respuesta incorrecta: 0 ms Su entrada [9,1,6] [0]

Stdout 1 6

Producto [9,1] Esperado [9,1,6]

Como puede ver, el código está perdiendo el 6. Sin embargo, el 6 se imprime en el bucle de análisis de elementos l1 restante. ¿Por qué se está perdiendo?

La única forma en que podría perderse si el ciclo no se ejecuta, lo que significa que el programa obtiene 6 como nulo, por lo tanto, omitiendo un valor. No estoy seguro de por qué está sucediendo. ¿Es esta la cadena de pensamiento correcta?

Cualquier información nueva o mejoras son muy apreciadas.

0
shiv 9 may. 2020 a las 23:43

3 respuestas

La mejor respuesta

Como un poco de promoción descarada, echa un vistazo a mi solución. Pero puedo señalar la razón por la que no funciona, y algunas otras cosas que son buenas prácticas En primer lugar, ¿para qué sirven b1 y b2? Me estoy perdiendo algo, porque no lo vi ni una sola vez en su código.

Aqui:

if(resBit >9){
    carryBit=1;
    resBit=resBit%10;
}

Estás configurando el bit de acarreo en 1. Sin embargo, debe establecerlo en sum / 10 en caso de que la suma surja en algo como 20. En el problema real, no hay ningún caso de prueba que le dé un problema con esto, sin embargo, con números más grandes esto causará errores.

La razón más grande es esta parte:

if(l1!=null){

Y

if(l2!=null){

Solo está comprobando si no es nulo una vez. Sin embargo, si la diferencia de tamaño de las dos listas es 2 o más, entonces l1 o l2 seguirán siendo nulos cuando finalice. Por lo tanto, debe cambiar el if a un bucle while.

Cuando apliqué estos cambios, funcionó. Aquí está el resultado:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //have to use bit addition here
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }

        int resBit = 0, carryBit=0;
        ListNode res = new ListNode(-1);
        ListNode dummy = res;

        while(l1!=null && l2!=null){
            resBit = l1.val+l2.val+carryBit;
            if(resBit >9){
                carryBit=resBit / 10;
                resBit=resBit%10;
            }
            else{
                carryBit=0;
            }
            dummy.next = new ListNode(resBit);
            l1=l1.next;
            l2=l2.next;
            dummy=dummy.next;
        }

        //add any remaining numbers to our result

        while(l1!=null){
            if(carryBit!=0){
                resBit = l1.val+carryBit;
                if(resBit >9){
                    carryBit=1;
                    resBit=resBit%10;
                }
                else{
                    carryBit=0;
                }
                dummy.next = new ListNode(resBit);
            }
            else{

                dummy.next = new ListNode(l1.val);
            }
            l1=l1.next;
            dummy=dummy.next;
        }

        while(l2!=null){
            if(carryBit!=0){
                resBit = l2.val+carryBit;
                if(resBit >9){
                    carryBit=1;
                    resBit=resBit%10;
                }
                else{
                    carryBit=0;
                }
                dummy.next = new ListNode(resBit);
            }
            else{
                dummy.next = new ListNode(l2.val);
            }
            l2=l2.next;
            dummy=dummy.next;
        }

        if(carryBit!=0){
            dummy.next = new ListNode(carryBit);
        }


        //remove the -1 used to create the LL initially
        res = res.next;

        return res;
    }
}
0
Higigig 9 may. 2020 a las 21:03

Hay una manera de omitir mi enfoque con errores, y la solución funciona. Sin embargo, todavía deja la pregunta original sin resolver.

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //have to use bit addition here
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }

        int b1=0, b2=0, resBit = 0, carryBit=0;
        ListNode res = new ListNode(-1);
        ListNode dummy = res;

        while(l1!=null || l2!=null){
            b1 = (l1 != null) ? l1.val : 0;
            b2 = (l2 != null) ? l2.val : 0;
            resBit = b1+b2+carryBit;
            if(resBit >9){
                carryBit=1;
                resBit=resBit%10;
            }
            else{
                carryBit=0;
            }
            dummy.next = new ListNode(resBit);
            if(l1!=null){
                l1=l1.next;
            }

            if(l2!=null){
                l2=l2.next;
            }

            dummy=dummy.next;
        }

        //add carry to our result if carry is not 0
        if(carryBit!=0){
            dummy.next = new ListNode(carryBit);
        }


        //remove the -1 used to create the LL initially
        res = res.next;
        return res;
    } 

Como dije, esta solución tiene éxito en el caso de prueba. Sin embargo, todavía no estoy seguro de por qué el código anterior no estaba funcionando. Responda si ve el motivo.

0
shiv 9 may. 2020 a las 21:01

// agregue cualquier número restante a nuestro resultado

    if(l1!=null){
        System.out.println(l1.val);
        if(carryBit!=0){
            resBit = l1.val+carryBit;
            if(resBit >9){
                carryBit=1;
                resBit=resBit%10;
            }
            else{
                carryBit=0;
            }
            dummy.next = new ListNode(resBit);
        }
        else{

            dummy.next = new ListNode(l1.val);
        }
        l1=l1.next;
        System.out.println(l1.val);
        dummy=dummy.next;
    }

    if(l2!=null){
        if(carryBit!=0){
            resBit = l2.val+carryBit;
            if(resBit >9){
                carryBit=1;
                resBit=resBit%10;
            }
            else{
                carryBit=0;
            }
            dummy.next = new ListNode(resBit);
        }
        else{
            dummy.next = new ListNode(l2.val);
        }
        l2=l2.next;
        dummy=dummy.next;
    }

    if(carryBit!=0){
        dummy.next = new ListNode(carryBit);
    }

Use while loop no si, en resumen.

Como puede ver, el código anterior se ejecuta solo una vez si alguno de los LinkedList se vuelve nulo. Y como su caso de prueba fue:

L1: [9,1,6]
L2: [0]

Como puede observar, después de la 1ra adición:

  • El puntero L1 se convierte en = {1}
  • El puntero L2 se convierte en {nulo}.

Entonces solo está agregando el puntero L1 una vez, no hasta que L1 se convierta en {nulo}.

Lo resolvió utilizando el ciclo while en la solución que proporcionó en los comentarios.

0
chuckskull 9 may. 2020 a las 22:33