方法1:列竖式求和
时间复杂度:$O(N)$, N = MAX{m, n}
空间复杂度:$O(1)$
解题思路
列竖式求和,逐位匹配处理。用carry保留进位。
Java 代码
class Solution {
public String addBinary(String a, String b) {
//双指针逆序遍历
int i = a.length() - 1;
int j = b.length() - 1;
//carry存储进位
int carry = 0;
StringBuilder sb = new StringBuilder();
//先遍历共同长度
while (i >= 0 && j >= 0) {
int sum = carry;
sum += a.charAt(i --) - '0';
sum += b.charAt(j --) - '0';
carry = sum / 2;
sb.append(sum % 2);
}
//如果a没遍历完
while (i >= 0) {
int sum = carry;
sum += a.charAt(i --) - '0';
carry = sum / 2;
sb.append(sum % 2);
}
//同理
while (j >= 0) {
int sum = carry;
sum += b.charAt(j --) - '0';
carry = sum / 2;
sb.append(sum % 2);
}
//i,j都遍历完,还有carry,则得进一位
if (carry == 1) {
sb.append(1);
}
return sb.reverse().toString();
}
}