【LeetCode】43. String multiplication

43. String multiplication

🧸 Reading questions

Give two strings , Multiply to get a string , This problem can't be solved by plastic surgery , Because the later test examples will be very large , plastic , Long plastic surgery can't be installed ！

🧸 Ideas

To multiply by bits , Save in string , Then add the strings obtained by the product , The final result is stored in the string in turn ,

🧸 Code

class Solution {
    
public:
string addStrings(string& count, string& sum)
{
    
    //end1,end2 Add from the tail of two numbers ,carry Record carry 
    int end1 = count.size() - 1, end2 = sum.size() - 1, carry = 0;
    string ret;// Record the sum of two numbers added 
    while (end1 >= 0 || end2 >= 0)
    {
    
        // If end1 Greater than 0  shows count There are also a number , be x1 take end1 The value of a , Otherwise take 0
        int x1 = 0;
        if (end1 >= 0)
        {
    
            x1 = count[end1] - '0';
            --end1;
        }
        int x2 = 0;
        if (end2 >= 0)
        {
    
            x2 = sum[end2] - '0';
            --end2;
        }

        //add Record the sum of two numbers added  , Plus carry , The first carry is 0
        int add = x1 + x2 + carry;
        // If add Greater than 9, It indicates that carry is required , also add To subtract 10
        // And enter the position 1 , Otherwise, enter the position 0, Otherwise, the carry will retain the result of the last carry , There will be errors 
        if (add > 9)
        {
    
            carry = 1;
            add -= 10;
        }
        else {
    
            carry = 0;
        }
        // Insert the remainder of the carry character at the end of  ret in , Turn it over later , To improve efficiency 
        ret += add;
    }
    // Come here , It means that both numbers have been added , But there is also carry 1 position , Insert the tail 
    if (carry != 0)
    {
    
        ret += carry;
        carry = 0;
    }
    // Flip 
    reverse(ret.begin(), ret.end());
	// Convert to numeric characters 
	for (auto& e : ret)
	{
    
		e += '0';
	}
    return ret;
}
string multiply(string num1, string num2) {
    
    if (num1 == "0" || num2 == "0")
    {
    
        return "0";
    }
    string count = "0";// Record the sum 
    int end1 = num1.size() - 1, end2 = num2.size() - 1;
    // Multiply by place ,num2 every  * num1 All bits 
    for (int i = end2; i >= 0; --i)
    {
    
        string sum;// Record product 
        int carry = 0;// Record carry 
        // When j = i when  , explain j Here you are . Is the last multiplication , Unwanted +0
        // When j-- after  j It's on the tenth , Multiply the number in the tens by other numbers , Directly in the back +1 individual 0, And so on 
        for (int j = end2; j > i; --j)
        {
    
            sum.push_back(0);
        }
        //i Control is num2 Flashback every bit of traversal 
        int x2 = num2[i] - '0';
        // The following is to use x2 * num1 every 
        for (int j = end1; j >= 0; --j)
        {
    
            int x1 = num1[j] - '0';
            int ret = x1 * x2 + carry;// Multiply two numbers + carry 
            sum += ret % 10;//sum Save a bit  , Tail insertion 
            carry = ret / 10;//carry Save ten 
        }
        // When two numbers are multiplied   Rounding and numbers , You need to   Carry tail interpolation 
        while (carry != 0) {
    
            sum += carry % 10;
            carry /= 10;
        }
        // After tail insertion   Flip strings 
        reverse(sum.begin(), sum.end());
        // Convert a string into a numeric string 
        for (auto &e : sum) {
    
            e += '0';
        }
        count = addStrings(count, sum);
    }
    return count;
}
};

🧸 Decoding code

The interpretation code has been written in the code comments ！

make blind and disorderly conjectures

This problem is done 2 Hours , Read the explanation of the question , Understand the solution step by step , Then I tried to write , Half understood , I will do it again several times in the future

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