LeetCode 67. Add Binary

題目

Given two binary strings, return their sum (also a binary string).

For example, a = "11" b = "1" Return "100".

翻譯

給兩個字元字串，回傳他們的總和(以字元字串回傳)。

範例：
a = '11'
b = '1' return '100'

思路

1. 一開始的想法是將a,b轉為數字，相加後再轉回bits，程式碼在下面，不過題目給的string長度轉成int時會超過int max，所以這個方法不能用
2. 改用純字串來處理，先處理位數一樣的部分，ex. "111"+"10" ，先處理"11"+"10"
3. 以 "11"+"10"為例，個位數1+0=1； 十位數1+1=2，因為bits是二進位，因此2->0，然後儲存進位資訊，這時候要回傳的字串為'10'
4. "111"最前面的"1"+剛才的進位1 = 2， 2-> 0 ， 會傳字串為'010'
5. 因為剛才還有進位，所以要把進位的1加到字串前面，最後回傳'1010'

解題

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    // 使用字串來處理
    var sumStr = "";
    var carry = 0;
    var longStr, shortStr;

    // 判斷a,b哪個字串比較長
    if(a.length > b.length){
        longStr = a;
        shortStr = b;
    } else {
        longStr = b;
        shortStr = a;
    }

    longStr = longStr.split("").reverse().join("");
    shortStr = shortStr.split("").reverse().join("");

    // 將短字串加到長字串裡面，這邊先計算到短字串的位數，ex. "110" + "1111"，這邊先處理 "110" + "111" 
    for(var i = 0 ; i < shortStr.length ; i++) {
        var c = parseInt(shortStr.charAt(i))+parseInt(longStr.charAt(i)) + carry;
        // 二進位，相加大於1，就要進位
        if(c > 1){
            carry = 1;
            c = c%2;
        } else {
            carry = 0;
        }

        sumStr = c + sumStr;
    }

    // 處理長字串剩下的字串
    for(var j =  shortStr.length  ; j <  longStr.length  ; j ++){
        var c = parseInt(longStr.charAt(j)) + carry;
        if(c > 1){
            carry = 1;
            c = c%2;
        } else {
            carry = 0;
        } 
        sumStr = c + sumStr
    }

    // 如果加完後還有進位，要放到字串最前面
    return (carry == 1 ? carry : "") + sumStr;
};

失敗的解題

var addBinary = function(a, b) {
    var sum = parseInt(a,2)+parseInt(b,2);
    var bitStr = "";

    while(sum > 0){
        bitStr = sum%2 + bitStr;
        sum = Math.floor(sum/2);
    }

    return bitStr == '' ? '0': bitStr ;
}