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

参考资料