【leetcode】The sword refers to Offer II 002. Binary addition

剑指 Offer II 002. 二进制加法

问题描述

给定两个 01 字符串 a 和 b ,请计算它们的和,并以二进制字符串的形式输出.

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

示例 1:

输入: a = "11", b = "10"
输出: "101"

示例 2:

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

提示：

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

题解

方法一：Add each one sequentially from back to front

Similar to storing multi-digit numbers in the form of a linked list and then implementing addition（如123+456=579,But the stored numbers are stored in the form of a linked list,即$1\to 2\to 3+4\to 5\to 6=5\to 7\to 9$）的一种思路.

步骤（以 a = “11”, b = “10” 为例）：

1. 把数字反转 —— a = “11”, b = “01”
2. Reverse the two numbers from front to back 每位 进行加.

The reason why it needs to be reversed is that there may be a carry-forward situation,Just like this example,After the addition, the carry needs to be filled in front 1.Of course this question stores numbers as strings,Naturally, it can be reversed,Because it's up front 1很方便,Each calculation is not difficult.But if it is a linked list with multiple digits,First, each calculation has to traverse the linked list to the next bit,假如两个4位数相加,就需要遍历4+3+2+1next two linked lists,This time complexity is very high;其次,It's also more complicated when it comes to carry.But in this case, it's really not necessary,Could be more simplified,这里只是提供个思路.

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        a = a[::-1]
        b = b[::-1]
        sum = ""
        jinwei = 0
        min_len = min(len(a), len(b))
        for i in range(min_len):
            c = int(a[i]) + int(b[i]) + jinwei
            if c < 2:
                sum += str(c)
                jinwei = 0
            else:
                sum += str(c % 2)
                jinwei = 1
        if len(a) == len(b):
            if jinwei:
                sum += str(jinwei)
            return sum[::-1]
        longer = a if len(a) > len(b) else b
        for i in range(min_len, len(longer)):
            c = int(longer[i]) + jinwei
            if c < 2:
                sum += str(c)
                jinwei = 0
            else:
                sum += str(c % 2)
                jinwei = 1
        if jinwei:
            sum += str(jinwei)
        return sum[::-1]

The code above is a bit complicated,改变一下,这样可能更容易理解.However, after multiple submissions, this time has always been greater than the time of the above code,The above code is generally beat80%-90%（32ms,36ms）,The following one can only beat30%左右（40ms,44ms）

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        i = len(a) - 1
        j = len(b) - 1
        sum = ""
        jinwei = 0
        while(i >= 0 or j >= 0):
            add_a = int(a[i]) if i >= 0 else 0
            add_b = int(b[j]) if j >= 0 else 0
            c = add_a + add_b + jinwei
            if c < 2:
                sum += str(c)
                jinwei = 0
            else:
                sum += str(c % 2)
                jinwei = 1
            i -= 1
            j -= 1
        if jinwei:
            sum += "1"
        return sum[::-1]

方法二：位运算

我们可以设计这样的算法来计算：

• 把 a 和 b 转换成整型数字 x 和 y,在接下来的过程中,x 保存结果,y 保存进位.
• 当进位不为 0 时
  计算当前 x 和 y 的无进位相加结果：answer = x ^ y
  计算当前 x 和 y 的进位：carry = (x & y) << 1
  完成本次循环,更新 x = answer,y = carry
• 返回 x 的二进制形式

为什么这个方法是可行的呢？在第一轮计算中,answer 的最后一位是 x 和 y 相加之后的结果,carry 的倒数第二位是 x 和 y 最后一位相加的进位.接着每一轮中,由于 carry 是由 x 和 y 按位与并且左移得到的,那么最后会补零,所以在下面计算的过程中后面的数位不受影响,而每一轮都可以得到一个低 i 位的答案和它向低 i + 1 位的进位,也就模拟了加法的过程.

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            sum = x ^ y
            jinwei = (x & y) << 1
            x, y = sum, jinwei
        return bin(x)[2:]