415. Add Strings

Leetcode 问题: 415. Add Strings

题目

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

You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.

传入两个非负整数字串 num1 及 num2,回传这两个字串的总和

不能直接将字串转换成整数然后做运算

Example

Input: num1 = "11", num2 = "123"
Output: "134"
Input: num1 = "456", num2 = "77"
Output: "533"
Input: num1 = "0", num2 = "0"
Output: "0"

演算法

1.

答案

JavaScript

function addStrings(decimalStringA, decimalStringB) {
    var addResultList = [];
    // 馀数:预设为 0
    var carry = 0;
    // Binary 字串 A 计算起始索引
    var decimalStringAIndex = decimalStringA.length - 1;
    // Binary 字串 B 计算起始索引
    var decimalStringBIndex = decimalStringB.length - 1;
    // 0 的 Ascii Code
    var zeroAsciiCode = '0'.charCodeAt(0);
    while (decimalStringAIndex >= 0 || decimalStringBIndex >= 0) {
        // 当两个 Binary 字串其中之一都还没运算到最后,继续运算
        // 总和加上之前的馀数
        var sum = carry;
        if (decimalStringAIndex >= 0) {
            // 当字串 A 检查长度大于 0,还可以加总运算
            // 取得 A 数字:从字串转换成整数
            var decimalANumber = decimalStringA.charCodeAt(decimalStringAIndex--) - zeroAsciiCode;
            // 加上目前 A 数字
            sum += decimalANumber;
        }
        if (decimalStringBIndex >= 0) {
            // 当字串 B 检查长度大于 0,还可以加总运算
            // 取得 B 数字:从字串转换成整数
            // 取得 A 数字:从字串转换成整数
            var decimalBNumber = decimalStringB.charCodeAt(decimalStringBIndex--) - zeroAsciiCode;
            // 加上目前 A 数字
            sum += decimalBNumber;
        }
        var remainNumber = sum % 10;
        // 将目前数字加入结果阵列
        addResultList.push(remainNumber);
        // 计算进位数字
        carry = Math.floor(sum / 10);
    }
    if (carry != 0) {
        // 如果还有进位数,将进位数加入
        addResultList.push(carry);
    }
    // 将阵列反转,并转换成字串
    var addResult = addResultList.reverse().join('');
    return addResult;
}

TypeScript

使用 Ascii Code 做字串转换数字运算

function addStrings(decimalStringA: string, decimalStringB: string): string {
    let addResultList = [];
    // 馀数:预设为 0
    let carry: number = 0;
    // Binary 字串 A 计算起始索引
    let decimalStringAIndex: number = decimalStringA.length - 1;
    // Binary 字串 B 计算起始索引
    let decimalStringBIndex: number = decimalStringB.length - 1;

    // 0 的 Ascii Code
    let zeroAsciiCode: number = '0'.charCodeAt(0);

    while (decimalStringAIndex >= 0 || decimalStringBIndex >= 0) {
        // 当两个 Binary 字串其中之一都还没运算到最后,继续运算
        // 总和加上之前的馀数
        let sum = carry;
        if (decimalStringAIndex >= 0) {
            // 当字串 A 检查长度大于 0,还可以加总运算
            // 取得 A 数字:从字串转换成整数
            let decimalANumber: number = decimalStringA.charCodeAt(decimalStringAIndex--) - zeroAsciiCode;
            // 加上目前 A 数字
            sum += decimalANumber;
        }

        if (decimalStringBIndex >= 0) {
            // 当字串 B 检查长度大于 0,还可以加总运算
            // 取得 B 数字:从字串转换成整数
            // 取得 A 数字:从字串转换成整数
            let decimalBNumber: number = decimalStringB.charCodeAt(decimalStringBIndex--) - zeroAsciiCode;
            // 加上目前 A 数字
            sum += decimalBNumber;
        }

        let remainNumber = sum % 10;
        // 将目前数字加入结果阵列
        addResultList.push(remainNumber);
        // 计算进位数字
        carry = Math.floor(sum / 10);
    }

    if (carry != 0) {
        // 如果还有进位数,将进位数加入
        addResultList.push(carry);
    }

    // 将阵列反转,并转换成字串
    let addResult = addResultList.reverse().join('');
    return addResult;
};

使用 JavaScript 内建的字串数字转换

function addStrings(decimalStringA: string, decimalStringB: string): string {
    let addResultList = [];
    // 馀数:预设为 0
    let carry: number = 0;
    // Binary 字串 A 计算起始索引
    let decimalStringAIndex: number = decimalStringA.length - 1;
    // Binary 字串 B 计算起始索引
    let decimalStringBIndex: number = decimalStringB.length - 1;

    while (decimalStringAIndex >= 0 || decimalStringBIndex >= 0) {
        // 当两个 Binary 字串其中之一都还没运算到最后,继续运算
        // 总和加上之前的馀数
        let sum = carry;
        if (decimalStringAIndex >= 0) {
            // 当字串 A 检查长度大于 0,还可以加总运算
            // 加上目前 A 数字
            sum += Number(decimalStringA[decimalStringAIndex]);
            decimalStringAIndex--;
        }

        if (decimalStringBIndex >= 0) {
            // 当字串 B 检查长度大于 0,还可以加总运算
            // 取得 B 数字:从字串转换成整数
            sum += Number(decimalStringB[decimalStringBIndex]);
            decimalStringBIndex--;
        }

        let remainNumber = sum % 10;
        // 将目前数字加入结果阵列
        addResultList.push(remainNumber);
        // 计算进位数字
        carry = Math.floor(sum / 10);
    }

    if (carry != 0) {
        // 如果还有进位数,将进位数加入
        addResultList.push(carry);
    }

    // 将阵列反转,并转换成字串
    let addResult = addResultList.reverse().join('');
    return addResult;
};

参考资料