给你两个二进制字符串,返回它们的和(用二进制表示)。
输入为 非空 字符串且只包含数字 1 和 0。
示例 1:
输入: a = “11”, b = “1”
输出: “100”
示例 2:
输入: a = “1010”, b = “1011”
输出: “10101”
提示:
每个字符串仅由字符 ‘0’ 或 ‘1’ 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 “0” ,就都不含前导零。
简单粗暴将其转化为字符数组里对应元素的求和处理
注意到’0‘对应ASCII码值为48
则可知,’0‘+1=’1’,’0‘+0=’1’,即‘0‘+(’1‘-’0‘)=’1‘,
也就是说当两个字符‘0’、‘1’运算时减去一个‘0’,就可以实现二进制中0+1=1
再具体处理一下进位的情况就可以实现二进制求和了
这是源代码
#include"iostream"
using namespace std;
class Solution
{
public:
string addBinary(string a, string b)
{
int al=a.size();
int bl=b.size();
//保证两个字符串要等长,在短的字符串前补上0
while(al>bl)
{
b='0'+b;//string型变量之间的+运算相当于把两者拼起来即 a+b=ab
bl++;
}
while(al<bl)
{
a='0'+a;
al++;
}
for(int i=al-1;i>0;i--)//从低位开始处理对应的位,另外处理最高位需要进位的情况
{
a[i]=a[i]-'0'+b[i];//a[i]=0+'0',或者1+'0'等等
if(a[i]>='2')//出现'1'+'1'的情况
{
if(a[i]=='2')
a[i]='0';
else
a[i]='1';//'11'+'11'='110'这种情况
a[i-1]+=1;//向高位进1
}
}
a[0]=a[0]-'0'+b[0];//将最高位进行相加
//最高位均为1的情况
if(a[0]>='2')
{
if(a[0]=='2')
a[0]='0';
else
a[0]='1';//'11'+'11'='110'这种情况
a='1'+a;
}
return a;
}
};
int main()
{
Solution sum;
string a;
string b;
cout<<"a=";cin>>a;
cout<<"b=";cin>>b;cout<<endl;
cout<<sum.addBinary(a,b);
return 0;
}
这是伪代码
class Solution//定义一个类
public: //公共访问权限
string addBinary(string a, string b)//定义一个字符串型的函数来对a、b两个字符串进行求和 int al ← 字符串a的长度
int bl ← 字符串b的长度
//保证两个字符串要等长,在短的字符串前补上0,等长不会进行下面两个循环
while al>bl //字符串b短的情况
b ← '0'+b //string型变量之间的+运算相当于把两者拼起来即 a+b=ab
bl ← bl+1 //b的长度加一
while al<bl //字符串a短的情况
a ← '0'+a
al ← al+1
//对字符串a,b进行同位的相加处理,从低位开始,另外处理最高位都为1的情况
for int i← 字符串a的长度-1 down to 1
a[i] ← a[i]-'0'+b[i] //相当于a[i]=0+'0',或者1+'0'等等
//出现1+1的情况,需要进位
if a[i]>='2' then
if a[i]='2' then
do a[i] ← '0'
else a[i]='3' then //这种情况为2+1,低位向高位已经进位过,即a[i+1]=b[i+1]=1
do a[i] ← '1'
do a[i-1] ← a[i-1]+1//向高位进1
end if
//现在处理最高位
a[0] ← a[0]-'0'+b[0];//将最高位进行相加
//最高位均为1的情况
if a[0]>='2' then
//操作同上
if a[0]='2' then //'11'+'10'这种情况
do a[0] ← '0'
else //'11'+'11'这种情况
do a[0] ← '1'
do a ← '1'+a //在前面接上1,即最高位为1+1,需要再进位
end if
return a //最后得到求和后的字符串
begin
Solution sum
string a,b
input a
input b
output sum.addBinary(a,b) //调用上面类内的函数,输出a,b的和
return 0
end