一、力扣算法：二进制求和

1、问题

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

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

示例 1:

输入: a = “11”, b = “1”
输出: “100”

示例 2:

输入: a = “1010”, b = “1011”
输出: “10101”

提示：

• 每个字符串仅由字符 ‘0’ 或 ‘1’ 组成。
• 1 <= a.length, b.length <= 10⁴
• 字符串如果不是 “0” ，就都不含前导零。

2、思路

思路一：

1. 创建 “指针 i” 和 “指针j” 分别指向指向 两个二进制字符串的 末位数字，从后向前遍历。
2. 以较长字符串为基准，如果无数字则用 0 填补。
3. 设置三个变量res、 tmp 和 carry , res用来保存最终计算完成的字符串，tmp用来保存相加后的 “当前位” 数值，carry用来保存相加后的 “进位” 数值。
4. tmp 由（a[i] + b[j] +carry) % 2 获得。
5. carry 由（a[i] + b[j] +carry) // 2 获得。
6. 若最终字符串遍历结束后，carry中仍有数值，则在res 前加 “1”。

思路二：
将二进制字符串转换为十进制，加和后再转换回二进制（注意：由于转换为二进制后，数值前会有0b，所以我们要取第二位之后的）。

3、解题代码

#coding:utf-8
class Solution:
    def addBinary1(self, a: str, b: str) -> str:
        res = ""
        i, j, carry = len(a) - 1, len(b) - 1, 0
        while i >= 0 or j >= 0:
            n1 = int(a[i]) if i >= 0 else 0
            n2 = int(b[j]) if j >= 0 else 0
            tmp = (n1 + n2 + carry) % 2
            carry = (n1 + n2 + carry) // 2
            res = str(tmp)+ res
            i, j = i - 1, j - 1
        return "1" + res if carry else res

    def addBinary2(self, c: str, d: str) -> str:
        return bin(int(c,2)+int(d,2))[2:]

if __name__ == "__main__":
    solution = Solution()
    print("******思路1*********")
    print("a为11，b为1 二进制求和为：{} ".format(solution.addBinary1("11", "1")))
    print("a为1010，b为1011 二进制求和为：{} ".format(solution.addBinary1("1010", "1011")))
    print("n******思路2*********")
    print("a为11，b为1 二进制求和为：{} ".format(solution.addBinary2("11", "1")))
    print("a为1010，b为1011 二进制求和为：{} ".format(solution.addBinary2("1010", "1011")))

4、时间与空间复杂度

时间复杂度：O(N)
N为较长字符串的长度

空间复杂度：O(1)

备注

1、问题来源：

力扣（LeetCode）
https://leetcode-cn.com/problems/add-binary

最后

以上就是跳跃百合为你收集整理的力扣算法：二进制求和一、力扣算法：二进制求和备注的全部内容，希望文章能够帮你解决力扣算法：二进制求和一、力扣算法：二进制求和备注所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。