leetcode中如何解決二進(jìn)制求和問(wèn)題

題目鏈接

https://leetcode-cn.com/problems/add-binary/

題目描述

給定兩個(gè)二進(jìn)制字符串，返回他們的和（用二進(jìn)制表示）。

輸入為非空字符串且只包含數(shù)字 1 和 0。

示例 1:

輸入: a = "11", b = "1"
輸出: "100"

示例 2:

輸入: a = "1010", b = "1011"
輸出: "10101"

解題方案

思路

• 標(biāo)簽：字符串

• 整體思路是將兩個(gè)字符串較短的用0補(bǔ)齊，使得兩個(gè)字符串長(zhǎng)度一致，然后從末尾進(jìn)行遍歷計(jì)算，得到最終結(jié)果

• 本題解中大致思路與上述一致，但由于字符串操作原因，不確定最后的結(jié)果是否會(huì)多出一位進(jìn)位，所以會(huì)有2種處理方式

• 第一種，在進(jìn)行計(jì)算時(shí)直接拼接字符串，會(huì)得到一個(gè)反向字符，需要最后再進(jìn)行翻轉(zhuǎn)

• 第二種，按照位置給結(jié)果字符賦值，最后如果有進(jìn)位，則在前方進(jìn)行字符串拼接添加進(jìn)位

• 時(shí)間復(fù)雜度：O(n)

代碼

• Java版本

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder ans = new StringBuilder();
        int ca = 0;
        for(int i = a.length() - 1, j = b.length() - 1;i >= 0 || j >= 0; i--, j--) {
            int sum = ca;
            sum += i >= 0 ? a.charAt(i) - '0' : 0;
            sum += j >= 0 ? b.charAt(j) - '0' : 0;
            ans.append(sum % 2);
            ca = sum / 2;
        }
        ans.append(ca == 1 ? ca : "");
        return ans.reverse().toString();
    }
}

• JavaScript版本

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    let ans = "";
    let ca = 0;
    for(let i = a.length - 1, j = b.length - 1;i >= 0 || j >= 0; i--, j--) {
        let sum = ca;
        sum += i >= 0 ? parseInt(a[i]) : 0;
        sum += j >= 0 ? parseInt(b[j]) : 0;
        ans += sum % 2;
        ca = Math.floor(sum / 2);
    }
    ans += ca == 1 ? ca : "";
    return ans.split('').reverse().join('');
};

畫(huà)解