Leetcode Langya list level 20 - binary sum

LeetCode The 20th floor of Langya list - Binary sum

Topic content

Topic link

---

Review of binary calculation rules

• Before exporting binary calculation rules , We might as well review the rules of decimal calculation
  • Dot into one , Borrow one for ten
• Binary calculation rules
  • On the two into one , Borrow one for two

---

Sample analysis

 Input  a = "11",b = "1"
 Output  "100"
 analysis :
		 We might as well make up the length of both of them , namely "011" And "001"
        1) 1  And  1  And   Corresponding carry addition  = 10 =>  The result above this bit is 0, Carry is 1[ Be careful , The initial carry is 0]
        2) 1  And  0  And   Corresponding carry addition  = 10 =>  The result in this position is 0, Carry is 1
        3) 0  And  0  And   Corresponding carry addition  = 1 =>  The result at this position is 1, Carry is 0

 Input  a = "11",b = "1"
 Output  "100"
 analysis :
		 We might as well make up the length of both of them , namely "011" And "001"
        1) 1  And  1  And   Corresponding carry addition  = 10 =>  The result above this bit is 0, Carry is 1[ Be careful , The initial carry is 0]
        2) 1  And  0  And   Corresponding carry addition  = 10 =>  The result in this position is 0, Carry is 1
        3) 0  And  0  And   Corresponding carry addition  = 1 =>  The result at this position is 1, Carry is 0

 Input  a = "1010",b = "1011"
 Output  "10101"
 analysis :
		 We might as well make up the length of both of them , namely "01010" And "01011"
        1) 1  And  0  And   Corresponding carry addition  = 1 =>  The result above this bit is 1, Carry is 0[ Be careful , The initial carry is 0]
        2) 1  And  1  And   Corresponding carry addition  = 10 =>  The result above this bit is 0, Carry is 1
        3) 0  And  0  And   Corresponding carry addition  = 1 =>  The result above this bit is 1, Carry is 0
        4) 1  And  1  And   Corresponding carry addition  = 10 =>  The result above this bit is 0, Carry is 1
        5) 0  And  0  And   Corresponding carry addition  = 1 =>  The result above this bit is 1, Carry is 0    

---

The derivation of algorithm thought

1. We find that every bit adds up to Add the corresponding two numbers to the corresponding carry to get the corresponding result
2. Put all the above results together , And then they Flip Come here is the final answer

---

Code implementation and Analysis

class Solution {
    public String addBinary(String a, String b) {
        // carry  This variable is used to record the size of the carry 
        var carry = 0;
        // len  This variable is used to record the length of a long string , See analysis for the function F
        var len = Math.max(a.length(),b.length());
        // res  This variable is used to splice the results 
        var res = new StringBuilder();
        // i The initialization , See analysis for the function S
        for (int i = 0; i < len; i++) {
            //  See parsing for code ideas T
            carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
            carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
            res.append((char) (carry % 2 + '0'));
            carry /= 2;
        }
        //  If the maximum length is exceeded , And carry , I.e. example 2, We need to take another place 1
        if (carry > 0) {
            res.append("1");
        }
        //  Just flip the result 
        return res.reverse().toString();
    }
}

analysis :

analysis F

• An important operation is proposed in the example analysis , Is to make up the length of their two strings to be the same , use len Record long string length , You can complement the length of their two strings to be consistent

analysis X

• First , Let's make it clear first , Our algorithm aims to start from the low order , And then gradually push to the high position , namely Low position -> High position
• secondly , Why don't we let i = len - 1 Well ?
  • If we let i = len - 1, If there is a short string, it will directly cross the boundary
  • Moreover, the judgment of string boundary will become more complicated
• Why do we let i = 0
  • from i < a.length() or i < b.length() It can be directly seen whether the boundary is crossed

analysis T

• If i < a.length, It means there is no cross-border , because carry yes int type , So the characters we get from it -'0' Get its corresponding integer number , Superimpose integer numbers on carry
• If i > a.length, It means that the border is crossed , According to the example , We need to make up the corresponding length where the length is insufficient , The figures to be added are 0, So directly 0 Overlay to carry that will do
• Empathy b
• take carry%2 + '0' The result of is cast to char Can be added to
  • Why cast ?
    • To get a character corresponding to an integer number , Instead of adding an integer number
  • Why? %2
    • Because the binary value range is {0,1}, So we need to %2
• take carry/=2
  • In order to get the result of rounding
    • such as 1 + 1 = 10 carry = 1, The conversion 10 Into the system is 1 + 1 = 2 , 2 / 2 = 1, Just get its carry

Algorithm is summarized

This algorithm is called the simulation method , It is the first method of the official solution , Method two involves in place operations , When I have finished the pre algorithm of bit operation , Then I will bring you the second solution to this problem