Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the force button algorithm continued to punch the card for the 20th day 🎈!
🚀 Algorithm 🚀

🌲 Example of original problem

Given two binary strings, return their sum (in binary).

The input is a non-empty string containing only the digits 1 and 0.

The sample1: Enter: a ="11", b = "1"Output:"100"
Copy the code
The sample2: Enter: a ="1010", b = "1011"Output:"10101"
Copy the code

Tip:

  • Each string consists only of the character ‘0’ or ‘1’.
  • 1 <= a.length, b.length <= 10^4
  • Strings that are not “0” have no leading zeros.

🌻C# method: traverse

Thinking analytical

The end result is the sum of binary numbers

We can start by zeroing in on the short binary string

Then each bit is traversed in reverse order, adding up the bits and recording the carry information.

Code:

public class Solution {
    public int[] PlusOne(int[] digits) {

        int len = digits.Length;
        for(int i = len - 1; i >= 0; i--) {
            digits[i]++;
            digits[i] %= 10;
            if(digits[i]! =0)
                return digits;
        }
        digits = new int[len + 1];
        digits[0] = 1;
        returndigits; }}Copy the code

The execution result

By execution time:76Ms, in all CBeat 93.10% of users in # submissionsMemory consumption:26MB, in all C# beat 25.51% of users in submission
Copy the code

🌻Java Method 1: Traversal

Thinking analytical

The whole idea is to complete the two shorter strings with 0, so that the length of the two strings is the same, and then perform traversal calculation from the end to get the final result.

In this problem, the general idea is the same as above, but because of string manipulation, it is not sure whether the final result will have an extra carry bit

So there are two ways to handle it:

  • The first kind of, directly concatenate the string during calculation, resulting in an inverted character, which needs to be flipped at last
  • The second,, assigns a value to the resulting character according to position, and adds a carry in front of the string concatenation if there is a carry

Code:

class Solution {
    public String addBinary(String a, String b) {
       StringBuilder ans = new StringBuilder();
        int ca = 0; // Whether to enter one
        for (int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0; i--, j--) {
            int sum = ca;
            sum += (i >= 0 ? a.charAt(i) - '0' : 0); If I <0, sum+=0; otherwise, the difference between the char type of '1' and that of '0' is exactly 1
            sum +=( j >= 0 ? b.charAt(j) - '0' : 0);If I <0, sum+=0; otherwise, the difference between the char type of '1' and that of '0' is exactly 1
            ans.append(sum % 2);  // If both are 1 then sum%2 should be exactly 0 otherwise 1
            ca = sum / 2;   // If both are 1 then ca should be exactly 1 otherwise 0
        }
        ans.append(ca == 1 ? ca : "");// Check whether there was a carry in the last calculation. If there is, add 1 to the front of the calculation
        returnans.reverse().toString(); }}Copy the code

The execution result

By execution time:2Ms, beat out all Java commits95.12% user memory consumption:38.4MB, beat out all Java commits64.87% of the userCopy the code

🌻Java Method 2: Brute force method

Thinking analytical

It’s just a matter of converting to decimal first and then going back to binary

class Solution {
    public String addBinary(String a, String b) {
        return Integer.toBinaryString(
            Integer.parseInt(a, 2) + Integer.parseInt(b, 2)); }}Copy the code

If the bits of A are N and the bits of B are m, the asymptotic time complexity of this algorithm is O(n+m).

💬 summary

  • Today is the twentieth day of the buckle algorithm clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!