一、leetcode算法
1、 二进制求和
1.1、题目
给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。
示例 1:
输入: a = “11”, b = “1”
输出: “100”
示例 2:
输入: a = “1010”, b = “1011”
输出: “10101”
1.2、思路
思路一：本题可以使用最简单的数学思想，将二进制都转化为十进制相加，然后再转化为二进制输出，但是转化为十进制后最数据的长度就有了限制，所以尽量不使用二进制向十进制转化的这种方式。
思路二：通过对二进制直接计算取得要返回的值，我们可以将两个二进制字符串逐位相加，逢二进一，最后得出要返回的字符串。这里需要注意的是低位相加后是否需要向高位进位，以及两个二进制字符串长度不一样，具体的需要怎么相加。
1.3、答案
class Solution { public String addBinary(String a, String b) { //new一个StringBuffer用来返回最后的字符串 StringBuffer ans = new StringBuffer(); //获取最长的字符串的长度，用来规定循环的次数,定义一个carry用来表示是哪个一个位置的进位 int n = Math.max(a.length(), b.length()), carry = 0; for(int i = 0; i < n; i++){ //计算上一个位置的进位，这里字符‘1’减去字符‘0’等于数字1 carry += i < a.length() ? (a.charAt(a.length() -1 - i) - '0') : 0; carry += i < b.length() ? (b.charAt(b.length() -1 - i) - '0') : 0; ans.append((char) (carry % 2 + '0')); //只有carry等于2的时候才能向上进一位，当carry等予0或者1的时候就不进位，所以这里除以2 carry /= 2; } //如果最后carry不等于0，证明有进位，则第一位加一 if(carry > 0){ ans.append('1'); } //因为是倒叙进行的进位计算，所以最终结果需要反转一下 ans.reverse(); return ans.toString(); } }
复杂度分析
时间复杂度：O(n)O(n)，这里的时间复杂度来源于顺序遍历 aa 和 bb。
空间复杂度：O(1)O(1)，除去答案所占用的空间，这里使用了常数个临时变量。
