生产型或服务型企业网站有哪些/aso推广优化

一、题目描述

给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为 非空 字符串且只包含数字 1 和 0。

示例 1:
输入: a = "11", b = "1"
输出: "100"

示例 2:
输入: a = "1010", b = "1011"
输出: "10101"

提示：

每个字符串仅由字符 '0' 或 '1' 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 "0" ，就都不含前导零。

二、解题思路

我们可以借鉴「列竖式」的方法，末尾对齐，逐位相加。在十进制的计算中「逢十进一」，二进制中我们需要「逢二进一」。

具体的，我们可以取n=max{∣a∣,∣b∣}，循环 n 次，从最低位开始遍历。我们使用一个变量carry 表示上一个位置的进位，初始值为 0。记当前位置对其的两个位为 ai和 bi ，则每一位的答案为 (carry+ai+bi)mod2，下一位的进位为 carry/2。重复上述步骤，直到数字 a 和 b 的每一位计算完毕。最后如果carry 的最高位不为 0，则将最高位添加到计算结果的末尾。

三、代码

1、自己写的

class Solution {public String addBinary(String a, String b) {int len1=a.length();int len2=b.length();int carry=0;String rs="";int i=len1-1;int j=len2-1;while(i>=0||j>=0){int c1=0;if(i>=0){c1=Integer.parseInt(String.valueOf(a.charAt(i--)));}int c2=0;if(j>=0){c2=Integer.parseInt(String.valueOf(b.charAt(j--)));}int s=c1+c2+carry;carry=s/2;rs=s%2+rs;}if(carry==1){rs=carry+rs;}return rs;}
}

2、官方的

class Solution {public String addBinary(String a, String b) {StringBuffer ans = new StringBuffer();int n = Math.max(a.length(), b.length()), carry = 0;for (int i = 0; i < n; ++i) {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;}if (carry > 0) {ans.append('1');}ans.reverse();return ans.toString();}
}

四、复杂度分析

假设 n=max{∣a∣,∣b∣}。

时间复杂度：O(n)，这里的时间复杂度来源于顺序遍历 a和 b。
空间复杂度：O(1)，除去答案所占用的空间，这里使用了常数个临时变量。

欢迎关注微信公众号【算法攻城师】