题解 | #二进制求和#
二进制求和
http://www.nowcoder.com/practice/1620262056c24c0e96de32fb261703d0
题意：
给定两个用字符串表示的二进制数，返回他们的和。
方法一：
模拟
思路：直接模拟。
逆序遍历字符串，实现对应位的相加求和运算；
并对进位进行判断，追加字符给结果字符串；
最后，反转结果字符串即可。
class Solution {
public:
string binaryAdd(string A, string B) {
int n1=A.size(),n2=B.size();
int flag=0;//进位标志
string res="";
for(int i=n1-1,j=n2-1;i>=0||j>=0;i--,j--){//逆向遍历
//计算求和
int t=flag;
if(i>=0)
t+=A[i]-'0';
if(j>=0)
t+=B[j]-'0';
if(t>=2){//判断进位
flag=1;
}else{
flag=0;
}
t%=2;
res+=t+'0';//追加字符
}
if(flag){//最后判断进位
res+='1';
}
reverse(res.begin(),res.end());//反转结果字符串
return res;
}
};
时间复杂度：%2C%E9%81%8D%E5%8E%86%E5%AD%97%E7%AC%A6%E4%B8%B2%E3%80%82)
空间复杂度：%2C%E5%B8%B8%E6%95%B0%E7%BA%A7%E5%88%AB%E5%AD%98%E5%82%A8%E7%A9%BA%E9%97%B4%E3%80%82)
方法二：
java
思路：java实现逆序模拟。
思路与方法一相同。
注意点：答案字符串追加字符串需要强制类型转换。
import java.util.*;
public class Solution {
public String binaryAdd (String A, String B) {
int n1=A.length(),n2=B.length();
int flag=0;//进位标志
StringBuffer res=new StringBuffer("");
for(int i=n1-1,j=n2-1;i>=0||j>=0;i--,j--){//逆向遍历
//计算求和
int t=flag;
if(i>=0)
t+=A.charAt(i)-'0';
if(j>=0)
t+=B.charAt(j)-'0';
if(t>=2){//判断进位
flag=1;
}else{
flag=0;
}
t%=2;
res.append((char)(t+'0'));//追加字符
}
if(flag==1){//最后判断进位
res.append('1');
}
//反转结果字符串
return res.reverse().toString();
}
}
时间复杂度：空间复杂度：
查看5道真题和解析
投递美团等公司10个岗位 >