【LeetCode】415. String addition

🧸 Reading questions

Put two strings use int Formal addition , The result is string Print .
This question cannot be used int/long Because the test cases are very long ,longlong I can't save it , So we have to calculate by bits ！

🧸 Code

Define two tags ned1/end2 Start at the end of the two arrays and move forward , And use carry Record carry ,
ret Calculate the sum of the two numbers , Addition of two numbers >10 be ret -= 10 ,carry Set up 1, otherwise carry Set up 0;
establish s The string appends the result of the calculation , Finally, turn it over ( This is to prevent , The header will always move the data , cause O(N²))

class Solution {
    
public:
    string addStrings(string num1, string num2) {
    
        int end1 = num1.size()-1,end2 = num2.size()-1;
        int carry = 0;
        string s;
        while(end1 >=0 ||end2>=0)
        {
    
            int x1 = 0;
            if(end1>= 0 )
            {
    
                x1 = num1[end1] - '0';
                --end1;
            }
            int x2 = 0;
            if(end2>= 0 )
            {
    
                x2 = num2[end2] - '0';
                --end2;
            }
            int ret = x1+x2 + carry;
            if(ret > 9)
            {
    
                ret-=10;
                carry = 1;
            }
            else
            {
    
                carry = 0;
            }
            s += ret + '0';
        }
        if(carry == 1)
        {
    
            s += '1';
        }
        reverse(s.begin(),s.end());
        return s;
    }
};

🧸 Decoding code

		 Define two tags , Forward access from the tail of the two arrays .
        int end1 = num1.size()-1,end2 = num2.size()-1;
         Definition carry Save carry 
        int carry = 0;
         Definition s Save results 
        string s;
         As long as one side of the cycle is not finished , I will continue to visit , because carry It may be worth , It is possible to carry all the time 
         for example ：9999+11 ,11 After walking ,carry = 1, therefore 9999 And continue to visit to know carry Be placed 0
        while(end1 >=0 ||end2>=0)
        {
    
        	x1x2 It is used for unit calculation   That is to say x1 = num1[end]
        	 Because every count has to be reset x1,x2
        	 therefore 
            int x1 = 0; 
             Judge end1 Have you finished , Keep counting before you finish , It's over x1 = 0
            if(end1>= 0 )
            {
    
                x1 = num1[end1] - '0';
                --end1;
            }
             Follow x1 Empathy 
            int x2 = 0;
            if(end2>= 0 )
            {
    
                x2 = num2[end2] - '0';
                --end2;
            }
            ret Is stored  x1+x2 Result 
            int ret = x1+x2 + carry;
             Calculated carry , If you add two numbers >9  be ret-=10, carry  = 1
            if(ret > 9)
            {
    
                ret-=10;
                carry = 1;
            }
            else
            {
    
            	 Must judge else , Otherwise, the carry may always be 1
                carry = 0;
            }
             The result of adding two numbers by tail interpolation 
            s += ret + '0';
        }
         It's over , If there is another number in the carry , And you have to put the tail in 
        if(carry == 1)
        {
    
            s += '1';
        }
         Finally, turn over and get the correct answer 
        reverse(s.begin(),s.end());
        return s;
    }

come on. I wish you get what you want offer！