415. Add Strings & 43. Multiply Strings

source: https://leetcode.com/problems/add-strings/

Question

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

• The length of both num1 and num2 is < 5100.
• Both num1 and num2 contains only digits 0-9.
• Both num1 and num2 does not contain any leading zero.
• You must not use any built-in BigInteger library or convert the inputs to integer directly.

相加

这题只考虑整数的情况，不考虑小数。

思路如下：

1. 逐位相加，取最大长度循环
2. 如果结果是二位数，下一次相加要多加1
3. 如果循环结束，仍有未加的借位，多加一位1

function addStrings(num1: string, num2: string): string {
    const arr1 = Array.from(num1).reverse();
    const arr2 = Array.from(num2).reverse();

    let borrow = false;
    const ret = [];

    for (let i = 0; i < (arr1.length > arr2.length ? arr1.length : arr2.length); i++) {
        const v = `${~~arr1[i] + ~~arr2[i] + (borrow ? 1 : 0)}`;
        if (v.length > 1) {
            borrow = true;
            ret.push(v[1]);
        } else {
            borrow = false;
            ret.push(v[0]);
        }
    }
    return [...ret, borrow ? '1' : ''].reverse().join('') || '0';
};

时间复杂度和空间复杂度都是O(n).

如果考虑小数，就是按.分开，各自相加，小数部分在整部部分有可能借位1.

Plus: 相乘

source: https://leetcode.com/problems/multiply-strings/

大致的思路是：

1. 每一位的数字做乘法
2. 每位要多加一个0
3. 然后用相加的方式相加

function multiply(num1: string, num2: string): string {
    const arr1 = Array.from(num1).reverse();
    const arr2 = Array.from(num2).reverse();

    let value = '0';
    for (let i = 0; i < arr2.length; i++) {
        let borrow = 0;
        const ret = [];
        for (let j = 0; j < arr1.length; j++) {
            const v = `${~~arr2[i] * ~~arr1[j] + borrow}`;
            if (v.length > 1) {
                borrow = ~~v[0];
                ret.push(v[1]);
            } else {
                borrow = 0;
                ret.push(v[0]);
            }
        }
        if (borrow) {
            ret.push(`${borrow}`);
        }
        let v = ret.reverse().join('') || '0';
        for (let j = 0; j < i; j++) {
            v = `${v}0`;
        }
        // addStrings => 415
        value = addStrings(value, v);
    }
    return value.replace(/^0+/g, '') || '0';
};

PlusPlus： 相减

这里还可以有一个进阶版，两个数相减。

相比两数相加，相减的难度在于要多判断一个负数的情况。

思路如下：

1. 用0补位
2. 和加法一样要考虑借位，只不过是减一
3. 要考虑负数的情况，我的想法是先比较大小，确定符号再大数减小数
4. 去掉多余的补位0

function subtractStrings(num1, num2) {
    // 补位0
    while (num1.length < num2.length) {
        num1 = '0' + num1;
    }
    while (num2.length < num2.length) {
        num2 = '0' + num2;
    }
    const isLarger = num1 >= num2;
    // 确定大数，小数和符号
    const [larger, less, symbol] = [...(isLarger ? [num1, num2] : [num2, num1]), isLarger ? '' : '-'];
    
    const arr1 = Array.from(larger).reverse();
    const arr2 = Array.from(less).reverse();

    let borrow = false;
    const ret = [];
    
    for (let i = 0; i < (arr1.length > arr2.length ? arr1.length : arr2.length); i++) {
        
        const isZero = arr1[i] === '0';

        // 0的话借位成10
        if (isZero) {
            arr1[i] = 10 - (borrow ? 1 : 0);
            borrow = true;
        } else {
            arr1[i] = ~~arr1[i] - (borrow ? 1 : 0);
            borrow = false;
        }

        // 借位的情况1x
        if (~~arr1[i] < ~~arr2[i]) {
            borrow = true;
            arr1[i] = ~~`1${arr1[i]}`;
        } else if (!isZero) {
            borrow = false;
        }

        const v = ~~arr1[i] - ~~arr2[i];
        ret.push(v);
    }
    if (borrow) ret[ret.length - 1] -= 1;
    return `${symbol}${ret.reverse().join('').replace(/^0+/g, '') || '0'}`;
};