title: 每日一練（39）：二進(jìn)制求和
categories:[劍指offer]
tags:[每日一練]
date: 2022/04/11
每日一練（39）：二進(jìn)制求和
給你兩個(gè)二進(jìn)制字符串亩进，返回它們的和（用二進(jìn)制表示）。
輸入為 非空 字符串且只包含數(shù)字 1 和 0缩歪。
示例 1:
輸入: a = "11", b = "1"
輸出: "100"
示例 2:
輸入: a = "1010", b = "1011"
輸出: "10101"
提示：
每個(gè)字符串僅由字符 '0' 或 '1' 組成镐侯。
1 <= a.length, b.length <= 10^4
字符串如果不是 "0" ，就都不含前導(dǎo)零驶冒。
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/add-binary
方法一：模擬運(yùn)算
思路分析
模擬直接計(jì)算，就是按照類似10進(jìn)制計(jì)算方式韵卤，考慮進(jìn)位
string addBinary(string a, string b) {
// 先倒序
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int na = a.size();
int nb = b.size();
int n = max(na, nb);
string res = "";
int curr = 0;
for (int i = 0; i < n; ++i)
{
curr += i < na ? a[i] == '1' : 0;
curr += i < nb ? b[i] == '1' : 0;
res.push_back(curr % 2 ? '1' : '0');
curr /= 2;
}
if (curr)
{
res.push_back('1');
}
reverse(res.begin(), res.end());
return res;
}
方法二：模擬運(yùn)算優(yōu)化（LeetCode英文網(wǎng)站大佬寫法）
思路分析
模擬直接計(jì)算骗污，就是按照類似10進(jìn)制計(jì)算方式，考慮進(jìn)位
string addBinary(string a, string b) {
string s;
s.reserve(a.size() + b.size());
int c = 0, i = a.size() - 1, j = b.size() - 1;
while(i >= 0 || j >= 0 || c == 1)
{
c += i >= 0 ? a[i--] - '0' : 0;
c += j >= 0 ? b[j--] - '0' : 0;
s.push_back((c & 1) + '0');
c >>= 1;
}
reverse(s.begin(), s.end());
return s;
}
