開源地址：https://github.com/jiauzhang/algorithms
題目描述
* https://leetcode-cn.com/problems/add-binary
* 給定兩個二進制字串，回傳他們的和(用二進制表示)，
* 輸入為非空字串且只包含數字 1 和 0，
*
* 示例 1:
* 輸入: a = "11", b = "1"
* 輸出: "100"
*
* 示例 2:
* 輸入: a = "1010", b = "1011"
* 輸出: "10101"
題目描述
* 1. 二進制運算相當簡單了，不同之處在于這里是操作的字串
* 所以需要程式實作字符相加的二進制運算
* 2. 兩個二進制字符相加，再加上進位位，總共有種可能的結果
* 0, 1, 2, 3，所以最直白的做法就是寫四個 if 陳述句即可
* 3. 但是為了進一步優化，我們可以定義一個陣列，如程式中所示
* 最后直接根據陣列獲取進位位的值和當前和的結果即可
* 本來需要四條 if 陳述句的操作直接一步就可以解決了！
題目描述
class Solution {
public:
string addBinary(string a, string b) {
if (a.size() < b.size()) {
do_add(b, a);
return b;
}
else {
do_add(a, b);
return a;
}
}
void do_add(string &a, string &b) {
char cs[4] = {0, 0, 1, 1};
char ss[4] = {'0', '1', '0', '1'};
char carry = 0;
char base = '0';
int i = a.size() - 1;
int j = b.size() - 1;
while (j >= 0 || (carry && i >= 0)) {
char sum = 0;
if (j >= 0) {
sum += b[j] - base;
}
sum += a[i] - base;
sum += carry;
a[i] = ss[sum];
carry = cs[sum];
i--;
j--;
}
if (carry)
a = '1' + a;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/10541.html
標籤：其他