LeetCode算法题-Add Binary(Java实现)

这是悦乐书的第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 小结

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

上一篇:LeetCode算法题-Count Primes(Java实现)


下一篇:LeetCode算法题-Rotated Digits(Java实现)