67. Add Binary

Leetcode 問題: 67. Add Binary
Categories:
Tags:

題目

Given two binary strings a and b, return their sum as a binary string.

傳入 2 個 binary 字串 a 及 b，回傳加總結果的 binary 字串

Example

Input: a = "11", b = "1"
Output: "100"

Input: a = "1010", b = "1011"
Output: "10101"

演算法

1. 當兩字串同個索引位置有數字

將數字字串轉換成數字整數，然後做加總

總數 = 數字 A + 數字 B + 進位

2. 計算餘數設定為加總結果

將加總數字 % 2取得餘數，求得加總結果加入結果

3. 計算進位數字

將加總數字 / 2 並無條件捨去，取得進位到下一個加總運算的數字

4. 處理剩餘的進位數字

數字都加總完，有可能進位了，然後剩下一個進位的數字，所以如果有剩餘的進位數字（非0），將剩餘的進位數字加入答案中

5. 輸出加總結果

因為加總運算是依序由個位十位，由小到大加入，較大的位數會在陣列最後方

所以要將陣列反轉再轉換成字串輸出才會是正確的答案

答案

JavaScript

function addBinary(binaryStringA, binaryStringB) {
    var addResultList = [];
    // 餘數：預設為 0
    var carry = 0;
    // Binary 字串 A 計算起始索引
    var binaryStringAIndex = binaryStringA.length - 1;
    // Binary 字串 B 計算起始索引
    var binaryStringBIndex = binaryStringB.length - 1;
    // 0 的 Ascii Code
    var zeroAsciiCode = '0'.charCodeAt(0);
    while (binaryStringAIndex >= 0 || binaryStringBIndex >= 0) {
        // 當兩個 Binary 字串其中之一都還沒運算到最後，繼續運算
        // 總和加上之前的餘數
        var sum = carry;
        if (binaryStringAIndex >= 0) {
            // 當字串 A 檢查長度大於 0，還可以加總運算
            // 取得 A 數字：從字串轉換成整數
            var StringANumber = binaryStringA.charCodeAt(binaryStringAIndex--) - zeroAsciiCode;
            // 加上目前 A 數字
            sum += StringANumber;
        }
        if (binaryStringBIndex >= 0) {
            // 當字串 B 檢查長度大於 0，還可以加總運算
            // 取得 B 數字：從字串轉換成整數
            var StringBNumber = binaryStringB.charCodeAt(binaryStringBIndex--) - zeroAsciiCode;
            // 加上目前 A 數字
            sum += StringBNumber;
        }
        var remainNumber = sum % 2;
        // 將目前數字加入結果陣列
        addResultList.push(remainNumber);
        // 計算進位數字
        carry = Math.floor(sum / 2);
    }
    if (carry != 0) {
        // 如果還有進位數，將進位數加入
        addResultList.push(carry);
    }
    // 將陣列反轉，並轉換成字串
    var addResult = addResultList.reverse().join('');
    return addResult;
}

TypeScript

使用 Ascii Code 做字串轉換數字運算

function addBinary(binaryStringA: string, binaryStringB: string): string {
    let addResultList = [];
    // 餘數：預設為 0
    let carry: number = 0;
    // Binary 字串 A 計算起始索引
    let binaryStringAIndex: number = binaryStringA.length - 1;
    // Binary 字串 B 計算起始索引
    let binaryStringBIndex: number = binaryStringB.length - 1;

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

    while (binaryStringAIndex >= 0 || binaryStringBIndex >= 0) {
        // 當兩個 Binary 字串其中之一都還沒運算到最後，繼續運算
        // 總和加上之前的餘數
        let sum = carry;
        if (binaryStringAIndex >= 0) {
            // 當字串 A 檢查長度大於 0，還可以加總運算
            // 取得 A 數字：從字串轉換成整數
            let StringANumber: number = binaryStringA.charCodeAt(binaryStringAIndex--) - zeroAsciiCode;
            // 加上目前 A 數字
            sum += StringANumber;
        }

        if (binaryStringBIndex >= 0) {
            // 當字串 B 檢查長度大於 0，還可以加總運算
            // 取得 B 數字：從字串轉換成整數
            let StringBNumber: number = binaryStringB.charCodeAt(binaryStringBIndex--) - zeroAsciiCode;
            // 加上目前 A 數字
            sum += StringBNumber;
        }

        let remainNumber = sum % 2;
        // 將目前數字加入結果陣列
        addResultList.push(remainNumber);
        // 計算進位數字
        carry = Math.floor(sum / 2);
    }

    if (carry != 0) {
        // 如果還有進位數，將進位數加入
        addResultList.push(carry);
    }

    // 將陣列反轉，並轉換成字串
    let addResult = addResultList.reverse().join('');
    return addResult;
};

使用 JavaScript 內建的字串數字轉換

function addBinary(binaryStringA: string, binaryStringB: string): string {
    let addResultList = [];
    // 餘數：預設為 0
    let carry: number = 0;
    // Binary 字串 A 計算起始索引
    let binaryStringAIndex: number = binaryStringA.length - 1;
    // Binary 字串 B 計算起始索引
    let binaryStringBIndex: number = binaryStringB.length - 1;

    while (binaryStringAIndex >= 0 || binaryStringBIndex >= 0) {
        // 當兩個 Binary 字串其中之一都還沒運算到最後，繼續運算
        // 總和加上之前的餘數
        let sum = carry;
        if (binaryStringAIndex >= 0) {
            // 當字串 A 檢查長度大於 0，還可以加總運算
            // 加上目前 A 數字
            sum += Number(binaryStringA[binaryStringAIndex]);
            binaryStringAIndex--;
        }

        if (binaryStringBIndex >= 0) {
            // 當字串 B 檢查長度大於 0，還可以加總運算
            // 取得 B 數字：從字串轉換成整數
            sum += Number(binaryStringB[binaryStringBIndex]);
            binaryStringBIndex--;
        }

        let remainNumber = sum % 2;
        // 將目前數字加入結果陣列
        addResultList.push(remainNumber);
        // 計算進位數字
        carry = Math.floor(sum / 2);
    }

    if (carry != 0) {
        // 如果還有進位數，將進位數加入
        addResultList.push(carry);
    }

    // 將陣列反轉，並轉換成字串
    let addResult = addResultList.reverse().join('');
    return addResult;
};

參考資料