Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

More and more testing positions, in addition to basic functional testing, programming background, scripting experience to stand out.

How can we improve our programming ability, brush LeetCode is one of the best way, not most of the words, brush the topic to go ~

I. Title Description:

  • The subject content

  • The subject sample

  • title

    • In this case, two strings are given. The two strings consist of 0 and 1
    • The problem requires the sum of the two binary strings
    • The input strings are non-empty strings

Ii. Analysis of Ideas:

When we get to this problem, the first thing that comes to mind is to simulate binary addition with 66.

Binary addition calculation: every two into one, there are four possible calculation process.

  • 0+0=0, -> is 0, and there is no carry
  • 0+1=1. If ->, the character is 1 without carry
  • If 1+1=2, -> is 0 and carries 1
  • 1+1+1=3. If ->, the character is 1 and the carry is 1

Because of the string form given in this question, we need to compare the two string lengths and complete the smaller string with “0”.

In Python, string is an immutable type that converts a string to a list to carry a change element

To clarify this, we use Python to implement the following code:

class Solution(object) :
    def addBinary(self, a, b) :
        """ :type a: str :type b: str :rtype: str """

        carry = 0

        if len(a) > len(b):
            index = len(a) - 1
            b = b.rjust(len(a), "0")
            Max = list(a)
        else:
            index = len(b) - 1
            a = a.rjust(len(b), "0")
            Max = list(b)

        while index >= 0:

            if int(a[index]) + int(b[index]) + carry == 0:
                Max[index] = "0"
                carry = 0

            elif int(a[index]) + int(b[index]) + carry == 2:
                
                Max[index] = "0"
                carry = 1

            elif int(a[index]) + int(b[index]) + carry == 3:
                Max[index] = "1"
                carry = 1

            elif int(a[index]) + int(b[index]) + carry == 1:

                Max[index] = "1"
                carry = 0
            index = index - 1

        if carry >= 1:
            Max = ['1'] + Max

        return "".join(Max)
Copy the code

Although, the implementation of the title requirements, but the code is too slag, we learn from the masters of excellent coding:

You don’t have to use any lists and zero completion.

  • The first is to concatenate the string directly while doing the calculation, resulting in an inverted character that needs to be flipped at the end
  • The second way is to assign values to the resulting characters by position, and finally, if there is a carry, add the carry in front of the string concatenation
class Solution(object) :def addBinary(self.a.b) : "" ":type a: str
        :type b: str
        :rtype: str"" "ans.extra = ' '.0 
        i,j=len(a)-1,len(b)-1
        while i>=0 or j>=0:
            if i >= 0:
                extra += ord(a[i]) - ord('0')
            if j >= 0:
                extra += ord(b[j]) - ord('0')
            ans += str(extra % 2)
            extra / / = 2
            i,j = i-1,j-1
        if extra == 1:
            ans += '1'
        return ans[::-1]
Copy the code

Iii. Summary:

We submitted our own code and the AC result was as follows:

Time O(n), space O(n), with a list.

Great code written by big guy, O(n) in time, O(1) in space.

The gap is clear. Keep trying.

That’s the content of this episode, please give your thumbs up and comments. See you next time