#67.Add Binary
Problem statement
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"
Explanation
給定兩個二進位制的字串 a
和 b
,將他們相加並返回二進位制的結果
Solution
將兩字串轉換成十進位,接著兩者相加得到總和,總和在轉換成二進位得到答案
public string AddBinary(string a, string b)
{
var x = Convert.ToInt32(a, 2);
var y = Convert.ToInt32(b, 2);
var res = x + y;
return Convert.ToString(res, 2);
}
測試沒問題直接提交,得到與上一題 Plus One 相同的錯誤,果然沒這麼簡單!於是我尋思著上一題的解法,這題用相同邏輯應該不會有問題,我朝著這個方向前進,建立一個 carry
變數來紀錄是否進位,以及 sb
來合併每次執行結果,上一題 Plus One 是對一個數加一,這題是兩個數相加,沒什麼太難的問題,只是有些小細節要注意
public string AddBinary(string a, string b)
{
// 將 a,b 補 0 直到相同長度
int maxLen = a.Length > b.Length ? a.Length : b.Length;
a = a.PadLeft(maxLen, '0');
b = b.PadLeft(maxLen, '0');
// true 表示進位, false 則無
bool carry = false;
StringBuilder sb = new StringBuilder();
int add;
maxLen--;
// 依據各種狀況進行相加
while (maxLen > -1)
{
add = a[maxLen] + b[maxLen];
if (add == 98) // a+b=2
{
if (carry)
sb.Insert(0, '1');
else
{
sb.Insert(0, '0');
carry = true;
}
}
else if (add == 97) // a+b=1
{
if (carry)
sb.Insert(0, '0');
else
sb.Insert(0, '1');
}
else // a+b=0
{
if (carry)
{
sb.Insert(0, '1');
carry = false;
}
else
sb.Insert(0, '0');
}
maxLen--;
}
if (carry) sb.Insert(0, '1');
return sb.ToString();
}
Reference
Thanks for reading the article 🌷 🌻 🌼
If you like it, please don't hesitate to click heart button ❤️
or click like on my Leetcode solution
or follow my GitHub ⭐
or buy me a coffee ⬇️ I'd appreciate it.
Top comments (0)