暴力法

首先，我們考慮一種最基本的方法：將 a 和 b 轉換為十進制數，然後求和，最後再將結果轉換為二進制數。

class Solution {
    fun addBinary(a: String, b: String): String {
        return Integer.toBinaryString(
            a.toInt(2) + b.toInt(2)
        )
    }
}

這種方法的時間複雜度為 ，其中 和 分別為 a 和 b 的位數長度。

然而，這種方法有一個限制。在 Kotlin 中，如果字串的位數超過一定的範圍，就無法進行轉換。例如：

• 超過 位就不能轉換為 Integer
• 超過 位就不能轉換為 Long
• 超過 位就不能轉換為 BigInteger

因此，對於長度較大的字串，我們需要一種更通用的算法。這種算法應該能夠處理任何長度的字符串，並且不依賴於 Kotlin 內建 parse 的功能。

來，一起準備面試吧！
讓我們一起寫一份超級吸睛的履歷吧！我們的專業建議會讓你的履歷表變得更加出色，幫助你用精練語句量化成效。別再猶豫了，動動手指投遞履歷吧！
立即加入 Line 讀書會，一起準備面試吧！

履歷諮詢	加入讀書會 (邀請碼：6171)

模擬

解題思路

我們可以參考「直式加法」，將 a 和 b 的尾端對齊，然後逐位相加。在十進制的計算中我們會「逢十進一」，而在二進制中我們需要「逢二進一」。

具體來說，我們首先找出 a 和 b 中位數較多的那一個，假設其位數為 。然後我們從最低位開始，遍歷這 位。我們使用一個變數 carry 來表示上一位的進位，初始值為 。假設當前位置對齊的兩個位數分別為 和 ，則每一位數的結果就是 ，而下一位的進位則是 。我們重覆這些步驟，直到 a 和 b 的每一位都計算完畢。最後如果 carry 的最高位不為 ，則將最高位加到計算結果的尾端。

為了讓各個位置對齊，可以先將代表二進制數字的字串反轉，然後從低位到高位遍歷。或者也可以直接把 a 和 b 中較短的那一個補 ，直到和較長的那一個一樣長，然後從高位向低位遍歷，並按順序將對應位置的結果存入答案字串中，最後再將答案字串反轉。

程式

class Solution {
    fun addBinary(a: String, b: String): String {
        var i = a.length - 1
        var j = b.length - 1
        var carry = 0
        var result = ""
        while (i >= 0 || j >= 0 || carry > 0) {
            val x = if (i >= 0) a[i] - '0' else 0
            val y = if (j >= 0) b[j] - '0' else 0
            val sum = x + y + carry
            carry = sum / 2
            val bit = sum % 2
            result = "$bit" + result
            i--
            j--
        }
        
        return result
    }
}

複雜度分析

首先，我們假設 為 和 中位數較多的那一個。

• 時間複雜度:
  。這是因為我們需要順序遍歷 a 和 b 的每一位，而 a 和 b 的位數最多為 。因此，時間複雜度與 成正比。

• 空間複雜度:
  。這是因為除了存儲答案所需的空間外，我們只使用了常數個 local variables。因此，空間複雜度為常數。

　更多 LeetCode 解答在此，一起來學習！

來，一起準備面試吧！

寫一份超級吸睛的履歷吧！從技術主管的視角，幫助你用精練語句量化成效

履歷諮詢	加入讀書會 (邀請碼：6171)