LeetCode剑指 Offer II 002. 二进制加法

给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。输入为 非空 字符串且只包含数字 1 和 0。
示例 1:
输入: a = “11”, b = “10”
输出: “101”

示例 2:
输入: a = “1010”, b = “1011”
输出: “10101”

提示：

每个字符串仅由字符 ‘0’ 或 ‘1’ 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 “0” ，就都不含前导零。

解题思路
二进制加法模拟：
第一步： 补零，如果字符串a与字符串b的长度不一致，那就需要补前导零，比如说a = “101110”, b =“101”;那就需要改变为a = “101110”; b = “000101”;
第二步： 从低位开始运算，使用整形数组存储加法后的值，比如说0+0=0， 0+1=1， 1+1=10；然后判断整形数组是否等于2产生二次进位。
第三步： 取反，从最高位开始取，如果最高位是0，那就需要抛弃。 第四步：返回值。

class Solution {
public String addBinary(String a, String b) {
int lenA = a.length(), lenB = b.length();
int len = lenA >= lenB ? lenA : lenB;
StringBuffer buffer = new StringBuffer();
// 补前导零
if(lenA > lenB){
for (int i = 0; i < lenA - lenB; i++) {
buffer.append('0');
}
buffer.append(b);
b = buffer.toString();
}else if(lenA < lenB){
for (int i = 0; i < lenB - lenA; i++) {
buffer.append('0');
}
buffer.append(a);
a = buffer.toString();
}
// 整形数组存储值，注意的是最高位的运算可能产生进位，也就是1+1=10的情况
int[] str = new int[len+1];
int temp = 0;
StringBuffer buffer1 = new StringBuffer();
// 从低位开始运算
for (int i = len-1; i >= 0; i--) {
if(a.charAt(i) == '1' && b.charAt(i) == '0'){
str[temp ++] += 1;
}else if(a.charAt(i) == '0' && b.charAt(i) == '1'){
str[temp ++] += 1;
}else if(a.charAt(i) == '1' && b.charAt(i) == '1'){
str[temp ++] += 0;
str[temp] += 1; // 这里产生了进位
}else if(a.charAt(i) == '0' && b.charAt(i) == '0'){
str[temp++] += 0;
}
// 产生进位，下一位运算还有0+1=1或者是1+0=1，这样子会再次产生一个进位，由于前面temp加1，这里的位置需要减1
// 找到原来值为2的位置
if(str[temp-1] == 2){
str[temp-1] = 0;
str[temp] = 1;
}
}
// 取反依次添加
for (int i = len; i >= 0; i--) {
// 如果最高为为零，那就抛弃
if(i == len && str[i] == 0){
continue;
}
buffer1.append(str[i]);
}
return buffer1.toString();
}
}

最后

以上就是迷路寒风为你收集整理的LeetCode剑指 Offer II 002. 二进制加法的全部内容，希望文章能够帮你解决LeetCode剑指 Offer II 002. 二进制加法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。