这是悦乐书的第157次更新，第159篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第16题（顺位题号是67）。给定两个二进制字符串，返回它们的总和（也是二进制字符串）。输入字符串都是非空的，只包含字符1或0。 例如：
输入：a =“11”，b =“1”
输出：“100”
输入：a =“1010”，b =“1011”
输出：“10101”
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
二进制数做加法时，是逢二进一，因为最后返回的是二进制字符串，所以可以不考虑溢出的风险。
先来运算一组简单的数据，使用提供的字符串“11”和“1”来演示。
“11”的最后一位是1，“1”的最后一位是1，两者相加等于2，此时两者的和的二进制字符串表示为“12”。因为逢二进一，所以最后一位变为0，向前进1，变成了“20”。同理，继续向前进1，此时二进制字符串变为了“100”，也就是我们最后要的结果。
依据上面的计算过程，我们可以分以下几个步骤来解题。
第一步，确定两个字符串长度中的最大值。因为要从后往前依次获取数字，循环的次数限制要以长度大的为准，长度小的默认是用0替代。定义一个变量carry存储上一次计算可能会遗留的值。创建一个StringBuilder对象，存储每次计算后要插入的字符串。
第二步，定义一个变量sum存储每次获得的数的和，初始值指向carry。分别获取两个字符串最后一位字符的整数，然后求和，对求得的和用2取余，然后将取余结果（0和1中的一个）插入第0个位置。
第三步，计算sum除以2的值，将其赋值给carry，接着循环第二步。
第四步，循环结束后，需要判断下carry是否等于0，因为carry最后一个计算sum/2得到的值有可能不等于0，如果不等于0，则将carry的值插入字符串第0个位置。
public String addBinary(String a, String b) {
int m = a.length();
int n = b.length();
int len = Math.max(m, n);
int carry = 0;
StringBuilder sb = new StringBuilder();
for (int i=0; i<len; i++) {
int sum = carry;
int num = 0;
if (m-1-i >= 0) {
num = a.charAt(m-1-i)-'0';
}
int num2 = 0;
if (n-1-i >= 0) {
num2 = b.charAt(n-1-i)-'0';
}
sum += num + num2;
sb.insert(0, sum%2+"");
carry = sum/2;
}
if (carry != 0) {
sb.insert(0, carry+"");
}
return sb.toString();
}03 第二种解法
对于第一种解法，可以适当再优化下，大体逻辑一致，不过在使用StringBuilder存储字符串的时候，使用的append方法，所以最后需要将其反转，才是最终我们需要的结果。
public String addBinary2(String a, String b) {
StringBuilder sb = new StringBuilder();
int i = a.length() - 1;
int j = b.length() -1;
int carry = 0;
while (i >= 0 || j >= 0) {
int sum = carry;
if (j >= 0) {
sum += b.charAt(j--) - '0';
}
if (i >= 0) {
sum += a.charAt(i--) - '0';
}
sb.append(sum % 2);
carry = sum / 2;
}
if (carry != 0) {
sb.append(carry);
}
return sb.reverse().toString();
}04 小结
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
- 还没有人评论，欢迎说说您的想法！
客服
