415. Add Strings

Leetcode 問題: 415. Add Strings
Categories:
Tags:

題目

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;
};

參考資料