current position:Home>leetcode 67. Add Binary(python)

leetcode 67. Add Binary(python)

2022-01-29 18:03:24 Wang Daya

This article has participated in 「 Digging force Star Program 」, Win a creative gift bag , Challenge creation incentive fund .

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 code 

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"
 Copy 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 code 

analysis

According to the meaning , Two examples including 0 and 1 String of binary digits , The title requires us to add the literal binary codes represented by these two strings , Then the binary result returned is also represented by a string . In fact, this question is to investigate the basic operational logic of addition , Actually, it can be used python The built-in function of , But the idea is simple , Write your own code :

  • initialization M and N obtain a and b The length of two strings , Guarantee a It must be the larger string
  • Then add them from the last bit , Full two, forward one
  • Until the traversal is finished b All characters of , Maybe a There are also characters that need to be traversed , Continue to a The remaining characters are added above
  • The string obtained at the end of traversal 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 code 

Running results

Runtime: 45 ms, faster than 10.19% of Python online submissions for Add Binary.
Memory Usage: 13.5 MB, less than 50.08% of Python online submissions for Add Binary.
 Copy code 

analysis

The above code is easy to understand , But it's too redundant , The concise version is as follows .

  • take a and b Convert to list a and b , Initialize carry variable tmp by 0 , result result Is an empty string

  • When a Not empty or b Not empty or tmp When it's not empty :

    (1) When a Not empty tmp += int(a.pop())

    (2) When b Not empty tmp += int(b.pop())

    (3) And then tmp%2 The obtained number of this position is spliced to result front

    (4)tmp Need Division 2

  • At the end of the loop result 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 code 

Running results

Runtime: 29 ms, faster than 34.94% of Python online submissions for Add Binary.
Memory Usage: 13.6 MB, less than 50.08% of Python online submissions for Add Binary.   
 Copy code 

analysis

Although I don't recommend using python The built-in function of , But when I use the above method to pass , I still feel itchy. I want to use the built-in function to solve it , Let's review the previous primary functions . Mainly used int Binary sum of bin Convert decimal integer to binary string result .

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 code 

Running results

Runtime: 26 ms, faster than 48.42% of Python online submissions for Add Binary.
Memory Usage: 13.6 MB, less than 22.38% of Python online submissions for Add Binary.        
        
 Copy code 

Original link :leetcode.com/problems/ad…

Your support is my greatest motivation

copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201291803217371.html

Random recommended