This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

describe

Given two binary strings a and b, return their sum as a binary string.

Example 1:

Input: a = "11", b = "1"
Output: "100"
Copy the code

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"
Copy the code

Note:

1 <= a.length, b.length <= 10^4
a and b consist only of '0' or '1' characters.
Each string does not contain leading zeros except for the zero itself.
Copy the code

parsing

We are asked to add the literal binary code represented by the two strings, and then return the binary result as a string. You can use python’s built-in functions to solve this problem quickly, but you should write your own code:

  • Initialize M and N to get the length of a and b, ensuring that A is the larger string
  • And then we’re going to add them up from the last digit, and we’re going to add them up by one
  • Continue to add the remaining characters of A until all characters of B have been traversed, at which point a may still have characters to traverse
  • The resulting string at the end of the loop is the answer

answer

class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        M, N = len(a), len(b)
        if M<N:
            a,b = b,a
            M,N = N,M
        i,j = M-1,N-1
        tmp = 0
        result = ''
        while i>-1 and j>-1:
            c = int(a[i])+int(b[j])
            if c + tmp > 1:
                result = str(c+tmp-2) + result
                tmp = 1
            else:
                result = str(c+tmp)+result
                tmp = 0
            i-=1
            j-=1
        while i>-1:
            c = int(a[i]) + tmp
            if c > 1:
                result = str(c - 2) + result
                tmp = 1
            else:
                result = str(c) + result
                tmp = 0
            i -= 1
        if tmp>0:
            result = '1' + result
        return result

        	      
		
Copy the code

The results

Given in the Python online submissions. Memory Usage: 10 ms Given in Python online submissions for Add Binary.Copy the code

parsing

The code above is easy to understand, but redundant. The concise version follows below.

  • Converts a and b to lists A and b, initializes the carry variable TMP to 0, and results in an empty string

  • When a is not empty or b is not empty or TMP is not empty:

    TMP += int(a.pop())

    TMP += int(b.pop())

    (3) Add TMP %2 to result

    TMP needs to be divisible by 2

  • The result at the end of the loop is the answer.

answer

class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        a = list(a)
        b = list(b)
        result = ''
        tmp = 0
        while a or b or tmp:
            if a:
                tmp += int(a.pop())
            if b:
                tmp += int(b.pop())
            result = str(tmp%2) + result
            tmp //= 2
        return result
Copy the code

The results

Given in the Python online submissions. Memory Usage: 10000 ms Given in the Python online submissions for Add Binary.Copy the code

parsing

While I don’t recommend using Python’s built-in functions to solve the problem, I still feel tempted to use the built-in functions after I’ve passed the above method, even if IT’s a refresher on the primitive functions. It uses the binary addition of int and bin to convert decimal integers into binary string results.

answer

class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        return  bin(int(a,2)+int(b,2))[2:]	  
Copy the code

The results

Given in the Python online submissions for Add Binary. Memory Usage: Given in the Python online submissions for Add Binary.Copy the code

Original link: leetcode.com/problems/ad…

Your support is my biggest motivation