时间戳

首页 > 解决方案 > 添加两个数字 leetcode 算法

javascript - 添加两个数字 leetcode 算法

问题描述

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

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

所以问题是

给定两个代表两个非负整数的非空链表。这些数字以相反的顺序存储，它们的每个节点都包含一个数字。将两个数字相加并将其作为链表返回。

您可以假设这两个数字不包含任何前导零，除了数字 0 本身。

为此我写了以下算法

/**
 * 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 编译器会在输入时将数组转换为链表。有人可以帮我弄清楚为什么我的输入可能会失败吗？

标签： javascript

解决方案

当 JavaScript 以科学计数法对数字进行字符串化时，将有一个+正指数符号。您看到的那个序列是1E+30，NaNs 代表+and E（因为恢复了顺序）。实际上，您可以在不知道这一点的情况下放置一个console.log(sum)orconsole.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)));

推荐阅读