攻城獅
Not a programmer 不工程的攻城獅

Not a programmer 不工程的攻城獅

LeetCode Solution, Easy, 67. Add Binary

加總二進制數值

攻城獅's photo
攻城獅
·May 8, 2022·

Subscribe to my newsletter and never miss my upcoming articles

67. Add Binary

題目敘述

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

Example 1:

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

Example 2:

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

Constraints:

  • 1 <= a.length, b.length <= 10**4
  • a and b consist only of '0' or '1' characters.
  • Each string does not contain leading zeros except for the zero itself.

題目翻譯

有兩個 Binary 的字串 ab,需要回傳其加總後的 Binary 字串。

解法解析

這題如果只是當純的將字串轉換成數值,很容易遇到一個問題就是會超出數值資料格式的範圍。可能就會需要使用到 BigInt 或類似 Long 的資料格式。所以比較好的方式是針對各個 Bit 作處理。

Bit-by-Bit Computation

這個解法很單純,就像是數值相加一樣,從個位數開始加,紀錄需要進位的值。

NM 分別是 ab 的字串長度 時間複雜度:O(max(N,M)) 空間複雜度:O(max(N,M))

Bit Manipulation

這解法主要使用了 Bitwise operator 來做處理。相加的話可以使用 XOR 來做處理,而是否需要進位的話則可以使用 ANDLeft shift 來處理。但是這個解法就會需要 Big Int 或是 Long 的資料型態。所以如果程式語言沒有支援的話,就不適合使用此解法。

NM 分別是 ab 的字串長度 時間複雜度:O(N+M) 空間複雜度:O(max(N,M))

解法範例

Go

Bit-by-Bit Computation

func addBinary(a string, b string) string {
    i, j, res, carry := len(a)-1, len(b)-1, "", 0
    for i >= 0 || j >= 0 {
        if i >= 0 {
            carry += int(a[i] - '0')
            i--
        }
        if j >= 0 {
            carry += int(b[j] - '0')
            j--
        }
        res = strconv.Itoa(carry%2) + res
        carry /= 2
    }
    if carry == 1 {
        return "1" + res
    }
    return res
}
Bit Manipulation
func addBinary(a string, b string) string {
    var x, _ = new(big.Int).SetString(a, 2)
    var y, _ = new(big.Int).SetString(b, 2)

    var sum = new(big.Int)
    var carry = new(big.Int)
    for y.Text(2) != "0" {
        sum.Xor(x, y)
        carry.And(x, y).Lsh(carry, 1)
        x.Set(sum)
        y.Set(carry)
    }
    return x.Text(2)
}

JavaScript

Bit-by-Bit Computation

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function (a, b) {
    const N = a.length,
        M = b.length;
    let r = '';
    let carry = false;
    for (let i = 0; i < Math.max(N, M); i++) {
        const da = a[N - i - 1] === '1',
            db = b[M - i - 1] === '1';

        const sum = (da !== db) !== carry;
        r += (sum ? '1' : '0');
        carry = (da && carry) || (db && carry) || (da && db);
    }

    return carry ? `1${r}` : r;
};
Bit Manipulation
/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function (a, b) {
    return (BigInt(`0b${a}`) + BigInt(`0b${b}`)).toString(2);
};

Kotlin


PHP

Bit-by-Bit Computation

class Solution
{

    /**
     * @param String $a
     * @param String $b
     * @return String
     */
    function addBinary($a, $b)
    {
        $n = max(strlen($a), strlen($b));
        $a = str_pad($a, $n, '0', STR_PAD_LEFT);
        $b = str_pad($b, $n, '0', STR_PAD_LEFT);
        $carry = 0;
        $answer = array();
        for ($i = $n - 1; $i >= 0; $i--) {
            if ($a[$i] == '1') {
                $carry++;
            }
            if ($b[$i] == '1') {
                $carry++;
            }

            $answer[] = strval($carry % 2);
            $carry = floor($carry / 2);
        }

        if ($carry == 1) {
            $answer[] = '1';
        }
        $answer = array_reverse($answer);
        return implode('', $answer);
    }
}
Bit Manipulation

Python

Bit-by-Bit Computation

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        n = max(len(a), len(b))
        a, b = a.zfill(n), b.zfill(n)

        carry = 0
        answer = []
        for i in range(n - 1, -1, -1):
            if a[i] == '1':
                carry += 1
            if b[i] == '1':
                carry += 1

            answer.append(str(carry % 2))
            carry //= 2

        if carry == 1:
            answer.append('1')
        answer.reverse()
        return ''.join(answer)
Bit Manipulation
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            x, y = x ^ y, (x & y) << 1
        return bin(x)[2:]

Rust


Swift


Did you find this article valuable?

Support 攻城獅 by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
 
Share this

Impressum

As smiple as possible