javascript - leetcode 两数相加算法

Question

我正在做以下leetCode问题:https://leetcode.com/problems/add-two-numbers/

我不确定为什么我的一个测试用例失败了

所以问题是

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

为此我编写了以下算法

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
const makeLinkedList = (inArr, i) => {
    if (i < 0) return null
    return { val:inArr[i], next:makeLinkedList(inArr, i-1)}
}


var addTwoNumbers = function(l1, l2) {
    let sum = 0
    let i = 1
    while(l1 || l2) {
        if (l1 && l2) {
            sum = sum + l1.val*i + l2.val*i
             l1 = l1.next
             l2 = l2.next
        } else {

        if (l1) {  
            sum = l1.val*i + sum
            l1 = l1.next
        }
        if (l2) {
            sum = l2.val*i + sum
            l2 = l2.next
        }    
      }
        i = i*10
    }
    const sumToString = sum.toLocaleString('fullwide', {useGrouping:false}); 
    return  makeLinkedList(sumToString, sumToString.length-1)
};

上面的代码我之所以使用while循环而不是递归调用函数，主要是为了使其更加优化。

无论如何，对于以下输入，我的测试用例失败

[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
[5,6,4]

即我的输出将是 [0,3,NaN,NaN,1] 而不是 [6,6,4,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]

请注意，leetCode 编译器会在输入时将数组转换为链表。有人可以帮助我找出为什么我的输入可能会失败吗？

Answer 1

当 JavaScript 将 scientific notation 中的数字字符串化时，会有一个 + 符号表示正指数。您看到的序列是 1E+30，NaN 代表 + 和 E(因为恢复顺序)。事实上，您可以放置​​一个 console.log(sum) 或 console.log(sumToString) 并在不知道这一点的情况下捕获问题，只需看看那里有什么。

并非所有语言都会告诉您它们可以在不损失精度的情况下存储的最大值，但 JavaScript 尤其如此，Number.MAX_SAFE_INTEGER包含值 9 007 199 254 740 991 因此它比 9E+15 多一点，远小于 1 + 1E+30 (较长的数字)。

你要做的就是像小学里学过的那样对数字进行加法:将两个数字相加，写出一个数字，然后看看是否有1可以进位到下一个数字-您要添加的配对。

迭代版本:

function makeLinkedList(arr,i){
  i=i || 0;
  return i<arr.length?{val:arr[i], next:makeLinkedList(arr,i+1)}:null;
}

var addTwoNumbers = function(l1, l2) {
  var snt={next:null};
  var cur=snt;
  var carry=0;
  while(l1 || l2 || carry){
    cur.next={next:null};
    cur=cur.next;
    var sum=(l1?l1.val:0)+(l2?l2.val:0)+carry;
    if(sum<10){
      cur.val=sum;
      carry=0;
    } else {
      cur.val=sum-10;
      carry=1;
    }
    l1=l1?l1.next:null;
    l2=l2?l2.next:null;
  }
  return snt.next;
}

var a=[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1];
var b=[5,6,4];
console.log(addTwoNumbers(makeLinkedList(a),makeLinkedList(b)));
a=[9,9];
b=[1,9];
console.log(addTwoNumbers(makeLinkedList(a),makeLinkedList(b)));

递归版本:

function makeLinkedList(arr,i){
  i=i || 0;
  return i<arr.length?{val:arr[i], next:makeLinkedList(arr,i+1)}:null;
}

var addTwoNumbers = function(l1, l2, carry) {
  if(!(l1 || l2 || carry))
    return null;
  carry=carry || 0;
  var sum=(l1?l1.val:0)+(l2?l2.val:0)+carry;
  return {
    val: sum % 10,
    next: addTwoNumbers(l1?l1.next:null,l2?l2.next:null,sum>9?1:0)
  };
}

var a=[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1];
var b=[5,6,4];
console.log(addTwoNumbers(makeLinkedList(a),makeLinkedList(b)));
a=[9,9];
b=[1,9];
console.log(addTwoNumbers(makeLinkedList(a),makeLinkedList(b)));