两数相加概况

十进制两数相加
二进制两数相加
链表式两数相加

解题思路

image.png

如果写过大数相加(字符串相加)，你可能会这么写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var addBinary = function(a, b) {
    let maxLen = Math.max(a.length,b.length)
    a = a.padStart(maxLen, '0')
    b = b.padStart(maxLen, '0')
    let flag = 0
    let res = ''
    let i = maxLen - 1
    while(i >= 0) {
        flag = Number(a[i]) + Number(b[i]) + flag
        res =  flag % 10 + res;
        flag = Math.floor(flag/10)
        i--
    }
    res = flag == 1 ? '1' + res : res
    return res
}

那如果换成二进制呢？是不是这样就好

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
let maxLen = Math.max(a.length,b.length)
    a = a.padStart(maxLen, '0')
    b = b.padStart(maxLen, '0')
    let flag = 0
    let res = ''
    let i = maxLen - 1
    while(i >= 0) {
        flag = Number(a[i]) + Number(b[i]) + flag
        res = flag % 2 + res;
        flag = Math.floor(flag/2)
        i--
    }
    res = flag == 1 ? '1' + res : res
    return res
};

细心的小伙伴已经看到端倪了，就是在取余和进位那里做了改变，其他的没动，所以我总结出一个N进制相加的通用方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {string} a
 * @param {string} b
 * @param {number} radix 进制数
 * @return {string}
 */
var addBinary = function(a, b, radix) {
let maxLen = Math.max(a.length,b.length)
    a = a.padStart(maxLen, '0')
    b = b.padStart(maxLen, '0')
    let flag = 0
    let res = ''
    let i = maxLen - 1
    while(i >= 0) {
        flag = Number(a[i]) + Number(b[i]) + flag
        res = flag % radix + res;
        flag = Math.floor(flag/radix)
        i--
    }
    res = flag == 1 ? '1' + res : res
    return res
};

另外一种字符串相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var addStrings = function(a, b) {
    let l1 = a.length - 1
    let l2 = b.length - 1
    let flag = 0
    let res = ''
    while(l1 >= 0 || l2 >= 0) {
        let x = l1 >=0 ? + a[l1] : 0
        let y = l2 >=0 ? + b[l2] : 0
        flag = x + y + flag
        res = flag % 10 + res;
        flag = Math.floor(flag/10)
        l1--
        l2--
    }
    res = flag == 1 ? '1' + res : res
    return res
};

链表式两数相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let dummy = new ListNode()
    let cur = dummy;
    let flag = 0
    while(l1 || l2) {
        let n1 = l1 && l1.val || 0
        let n2 = l2 && l2.val || 0
        let total = n1 + n2 + flag
        cur.next = new ListNode(total % 10)
        cur = cur.next
        l1 = l1 && l1.next
        l2 = l2 && l2.next
        flag = Math.floor(total / 10)
    }
    if (flag) {
        cur.next = new ListNode(flag)
    }
    return dummy.next
};