LeetCode --- 字符串、数组
简书专栏：//www.greatytc.com/nb/41796568
知乎专栏：https://zhuanlan.zhihu.com/c_174823416
一、题目描述
来源：力扣（LeetCode）
给定两个二进制字符串，返回他们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0。
示例:
输入: a = "11", b = "1"
输出: "100"
输入: a = "1010", b = "1011"
输出: "10101"
二、实现思路以及代码
- 首先明确两个数相加，是从后往前加，那么可以定义两个指针i,j从后向前遍历，直到其中一个小于0的时候结束循环。相加的关键是在于处理进位的问题。
- 单独定义一个变量up来控制，当两数之和加上up大于1时，表明需要向后进位，向结果字符串的首位置插入当前总和减去2（因因为总和大于1，说明可能是1+1+1或1+1+0的形式，减去2之后即为进位之后留在此处的数字）。
- 否则表明不需要进位，直接在字符串首位插入该总和。
- 结合代码加以理解
public static String addBinary(String a, String b) {
int i = a.length() - 1;
int j = b.length() - 1;
StringBuffer br = new StringBuffer();
//定义进位变量
int up = 0;
//定义相加之和
int sum = 0;
//注意这里用的是或，不是且，因为如果两个字符串长度不一致，剩余的也要加上去
while (i >= 0 || j >= 0) {
//上次的进位作为本次sum的初始值
sum = up;
if (i >= 0) {
sum += a.charAt(i) - '0';
i--;
}
if (j >= 0) {
sum += b.charAt(j) - '0';
j--;
}
if (sum > 1) {
up = 1;
sum -= 2;
} else {
up = 0;
}
br.insert(0, sum);
}
//最后一位进位要加上
if (up == 1) {
br.insert(0, 1);
}
return br.toString();
}
更为简洁的代码：
public String addBinary(String a, String b) {
StringBuffer sb = new StringBuffer();
int i = a.length() - 1, j = b.length() - 1;
int carry = 0;
while(i >= 0 || j >=0) {
int ta = i >= 0 ? (a.charAt(i) - '0') : 0;
int tb = j >= 0 ? (b.charAt(j) - '0') : 0;
int sum = ta + tb + carry;
carry = sum / 2;
sum = sum % 2;
sb.append(sum);
i--;
j--;
}
if(carry == 1) {
sb.append("1");
}
return sb.reverse().toString();
}
三、测试代码
public static void main(String[] args) {
String a = "11";
String b = "1";
System.out.println(addBinary(a, b));
a = "1101";
b = "11";
System.out.println(addBinary(a, b));
}
输出结果为：
100
10000
