AC 剑指 Offer II 002. 二进制加法
2022-03-22 本文已影响0人
itbird01
给定两个 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" ,就都不含前导零。
class Solution {
/**
* @Title: addBinary
* @Description: 字符串翻转+补0+进位
* @author: itbird
* @date 2022年3月21日 下午8:12:08
* @param a
* @param b
* @return String 时间复杂度: O(N) 空间复杂度: O(N)
*/
public String addBinary(String a, String b) {
int k = a.length() - b.length();
StringBuilder aBuilder = new StringBuilder(a).reverse();
StringBuilder bBuilder = new StringBuilder(b).reverse();
// 补0
if (k > 0) {
for (int i = 0; i < k; i++) {
bBuilder.append('0');
}
} else {
for (int i = 0; i < Math.abs(k); i++) {
aBuilder.append('0');
}
}
int flag = 0;
StringBuilder reStringBuilder = new StringBuilder();
for (int i = 0; i < aBuilder.length(); i++) {
int temp1 = aBuilder.charAt(i) - '0';
int temp2 = bBuilder.charAt(i) - '0';
int temp = temp1 + temp2 + flag;
if (temp == 3) {
flag = 1;
reStringBuilder.append('1');
} else if (temp == 2) {
flag = 1;
reStringBuilder.append('0');
} else if (temp == 1) {
flag = 0;
reStringBuilder.append('1');
} else {
flag = 0;
reStringBuilder.append('0');
}
}
if (flag == 1) {
reStringBuilder.append('1');
}
return reStringBuilder.reverse().toString();
}
}