题解 | #二进制求和#
二进制求和
http://www.nowcoder.com/practice/1620262056c24c0e96de32fb261703d0
题意理解
把两个字符串格式的二进制数字相加,求和的结果也用字符串的二进制数表示。
方法一
高精度加法
把字符串二进制数字转换成数组格式,每一位对应于数组中的一个整型元素。两个数组a,b从位置0开始表示二进制数的最低位(即倒序),在每一个位置上做加法操作,并计算是否要进位。当较短的数字的每一位都加完后,单独处理另外一个数组剩下的位。
示意图如下:
具体代码如下:
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param A string字符串
* @param B string字符串
* @return string字符串
*/
string binaryAdd(string A, string B) {
// write code here
vector<int> a,b,c;
string s;
for (int i=A.size()-1;i>=0;i--)
{
a.push_back(A[i]-'0');
}
for (int i=B.size()-1;i>=0;i--)
{
b.push_back(B[i]-'0');
}
int i = 0, jinwei = 0;
while (i<A.size() && i<B.size())
{
//计算结果的每一位和进位
c.push_back((a[i]+b[i]+jinwei)%2);
jinwei = (a[i]+b[i]+jinwei)/2;
i++;
}
//处理剩余的数字
if (i==A.size())
{
while (i<B.size())
{
c.push_back((b[i]+jinwei)%2);
jinwei = (b[i]+jinwei)/2;
i++;
}
}
else
{
while (i<A.size())
{
c.push_back((a[i]+jinwei)%2);
jinwei = (a[i]+jinwei)/2;
i++;
}
}
if (jinwei) c.push_back(1);
for (int j=c.size()-1;j>=0;j--)
{
s = s + to_string(c[j]);
}
return s;
}
};
时间复杂度: 。对于字符串A,B和数组a,b都遍历了一遍,长度统一用N表示。
空间复杂度: 。使用数组a,b,c存储二进制数字,长度均为N。
方法二
异或
使用异或来计算二进制中每一位的加法,当两个数字相同时,异或结果为0;两个数字不同时,异或结果为1。同样的,进位也要加入异或运算。
具体代码如下:
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param A string字符串
* @param B string字符串
* @return string字符串
*/
string binaryAdd(string A, string B) {
// write code here
string s;
int jinwei = 0, i;
int n = A.size()-1, m = B.size()-1;
for (i=0;i<=n && i<=m;i++)
{
//使用异或进行计算
s = s + to_string(A[n-i]^B[m-i]^jinwei);
if ((A[n-i]==B[m-i] && A[n-i]=='1') || (A[n-i]!=B[m-i] && jinwei))
jinwei = 1;
else jinwei = 0;
}
//处理剩余的位数
if (i==(n+1))
{
while (i<=m)
{
s = s + to_string((B[m-i]-'0')^jinwei);
jinwei = jinwei && (B[m-i]=='1');
i++;
}
}
else
{
while (i<=n)
{
s = s + to_string((A[n-i]-'0')^jinwei);
jinwei = jinwei && (A[n-i]=='1');
i++;
}
}
if (jinwei) s = s + '1';
reverse(s.begin(), s.end());
return s;
}
};
时间复杂度: 。对于字符串A,B都遍历了一遍,长度统一用N表示。
空间复杂度: 。使用字符串s存储最后的结果。