本文共 2649 字，大约阅读时间需要 8 分钟。
给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1"输出: "100"
示例 2:
输入: a = "1010", b = "1011"输出: "10101"
提示：
'0' 或 '1' 组成。1 <= a.length, b.length <= 10^4"0" ，就都不含前导零。解题方案
思路整体思路是将两个字符串较短的用 000 补齐，使得两个字符串长度一致，然后从末尾进行遍历计算，得到最终结果。
本题解中大致思路与上述一致，但由于字符串操作原因，不确定最后的结果是否会多出一位进位，所以会有 2 种处理方式：
第一种，在进行计算时直接拼接字符串，会得到一个反向字符，需要最后再进行翻转
第二种，按照位置给结果字符赋值，最后如果有进位，则在前方进行字符串拼接添加进位时间复杂度：O(n)O(n)O(n)
官方版解法：
class Solution { public String addBinary(String a, String b) { StringBuilder ans = new StringBuilder(); int ca = 0; for(int i = a.length() - 1, j = b.length() - 1;i >= 0 || j >= 0; i--, j--) { int sum = ca; sum += i >= 0 ? a.charAt(i) - '0' : 0; sum += j >= 0 ? b.charAt(j) - '0' : 0; ans.append(sum % 2); ca = sum / 2; } ans.append(ca == 1 ? ca : ""); return ans.reverse().toString(); }} 民间版：
public String addBinary(String a, String b) { if (a.equals(b) && a.equals("0")) { return "0"; } int maxlen = a.length()>b.length()?a.length():b.length(); int[] inta = new int[maxlen]; int[] intb = new int[maxlen]; int[] res = new int[maxlen]; Arrays.fill(inta, 0); Arrays.fill(intb, 0); Arrays.fill(res, 0); int cusora = maxlen-1; char[] stra = a.toCharArray(); for (int i = stra.length-1; i >= 0; i--) { inta[cusora] = stra[i] - '0'; cusora--; } int cusorb = maxlen-1; char[] strb = b.toCharArray(); for (int i = strb.length-1; i >= 0; i--) { intb[cusorb] = strb[i] - '0'; cusorb--; } int index = maxlen-1; boolean flag = false; while (index > 0) { int count = inta[index] + intb[index]; if (count == 2 && !flag) { res[index] = 0; flag = true; index--; }else if (count == 2 && flag) { res[index] = 1; flag = true; index--; }else if (count == 0 && flag) { res[index] = count+1; flag = false; index--; }else if (count == 0 && !flag) { res[index] = count; flag = false; index--; }else if (count == 1 && !flag) { res[index] = count; flag = false; index--; }else if (count == 1 && flag) { res[index] = 0; flag = true; index--; } } //index=0 int count = inta[index] + intb[index]; String string = null; if (count ==2 && flag) { string = "11"; }else if (count ==2 && !flag) { string = "10"; }else if (count==0 && !flag) { string = ""; }else if (count==0 && flag) { string = "1"; }else if (count==1 && !flag) { string = "1"; }else if (count==1 && flag) { string = "10"; } for (int i = 1; i < res.length; i++) { string+=res[i]; } return string; }
转载地址：http://ybuqb.baihongyu.com/