Given two binary strings, return their sum (also a binary string).

For example,
a =?"11"
b =?"1"
Return?"100".

思路：逐位相加，進(jìn)位保留在和的下一位中。

?

C++實(shí)現(xiàn)代碼：

#include<iostream> #include<string> #include<vector> using namespace std;class Solution { public:string addBinary(string a, string b){int size1=a.size()-1;int size2=b.size()-1;int size=max(size1,size2);string digits(size+1,'0');while(size1>=0&&size2>=0){if((a[size1]=='1')&&(b[size2]=='1')){digits[size-1]='1';if(size1==0&&size2==0)digits.insert(digits.begin(),'1');size1--;size2--;size--;}else if(((a[size1]=='1')||(b[size2]=='1'))&&(digits[size]=='0')){digits[size]='1';size1--;size2--;size--;}else if(((a[size1]=='1')||(b[size2]=='1'))&&(digits[size]=='1')){digits[size]='0';digits[size-1]='1';if(size1==0&&size2==0)digits.insert(digits.begin(),'1');size1--;size2--;size--;}else{digits[size]=digits[size];size1--;size2--;size--;}}cout<<digits<<endl;if(size1>=0){while(size1>=0&&size>=0){if((digits[size]=='1')&&(a[size1]=='1')){digits[size]='0';digits[size-1]='1';if(size==0)digits.insert(digits.begin(),'1');size1--;size--;}else if((digits[size]=='1')&&(a[size1]=='0')){size1--;size--;}else{digits[size]=a[size1];size--;size1--;}}}if(size2>=0){while(size2>=0&&size>=0){if((digits[size]=='1')&&(b[size2]=='1')){digits[size]='0';digits[size-1]='1';//最前面兩個(gè)數(shù)相加需要進(jìn)位的時(shí)候，在前面插入1if(size==0)digits.insert(digits.begin(),'1');size2--;size--;}else if((digits[size]=='1')&&(b[size2]=='0')){size2--;size--;}else{digits[size]=b[size2];size--;size2--;}}}return digits;} }; int main() {string b="100";string a="110010";Solution s;cout<<"digits: "<<s.addBinary(a,b)<<endl; }

?只能想到這么麻煩的方法，哎。。。

string addBinary(string a, string b) {if(a.empty())return b;if(b.empty())return a;int carry=0;int i=a.size()-1;int j=b.size()-1;string res;int sum=0;while(i>=0&&j>=0){sum=a[i--]-'0'+b[j--]-'0'+carry;if(sum>=2){char c=sum%2+'0';res=c+res;carry=1;}else{char c=sum+'0';res=c+res;carry=0;}}while(i>=0){sum=carry+a[i--]-'0';if(sum>=2){char c=sum%2+'0';res=c+res;carry=sum/2;}else{char c=sum+'0';res=c+res;carry=0;}}while(j>=0){sum=carry+b[j--]-'0';if(sum>=2){char c=sum%2+'0';res=c+res;carry=sum/2;}else{char c=sum+'0';res=c+res;carry=0;}}if(carry==1)res.insert(0,"1");return res;}

?

總結(jié)

以上是生活随笔為你收集整理的Add Binary的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。