leetcode[43] Multiply Strings

问题描述：

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Note:

1. The length of both num1 and num2 is < 110.
2. Both num1 and num2 contain only digits 0-9.
3. Both num1 and num2 do not contain any leading zero, except the number 0 itself.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

题意就是两个大数相乘，但是不能用库函数。

解题思路：

解题思路就是字符串每一位相乘最后相加，每次得到与num2某一位相乘的结果，最后加起来。

源码：

我的代码（怎一搓字了得）：

class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1=="0" || num2=="0")  return "0";
        string result;
        int i=num2.length();
        while(i--){
            string yf = submultiply(num1, num2[i]);
            // yf.append(num2.length()-i-1, "0");
            for(int j=0; j<num2.length()-i-1; j++)
                yf = yf + "0";
            // cout<<yf<<" "<<result<<" "<<i<<endl;
            result = add(result, yf);
        }
        return result;
    }
    string submultiply(string num1, char num2){
        if(num1=="0" || num2=='0')  return "0";
        string result;
        int i=num1.length();
        int flag=0;
        while(i--){
            int tmp = (num1[i]-'0') * (num2-'0')+flag;
            flag = tmp/10;
            tmp = tmp%10;
            result.insert(0, to_string(tmp));
        }
        if(flag!=0)
            result.insert(0, to_string(flag));
        return result;
    }
    string add(string num1, string num2){
        if(num1=="")    return num2;
        if(num2[0]=='0')   return num1;
        // num2 = num2+"0";
        int i=num2.length();
        int j=num1.length();
        int flag=0;
        string result;
        while(i--){
            j--;
            int tmp;
            if(j>=0){
                tmp = (num2[i]-'0') + (num1[j]-'0')+flag;
            }
            else    tmp = (num2[i]-'0')+flag;
            flag = tmp/10;
            tmp = tmp%10;
            result.insert(0, to_string(tmp));
        }
        if(flag!=0)
            result.insert(0, to_string(flag));
        return result;
    }
};

大佬的代码：

class Solution {
public:
	string multiply(string num1, string num2) {
		string res(num1.size() + num2.size(), '0');
		for (int i = num1.size() - 1; i >= 0; --i) {
			int carry = 0;
			for (int j = num2.size() - 1; j >= 0; --j) {
				int tmp = (res[i + j + 1] - '0') + (num2[j] - '0')*(num1[i] - '0') + carry;
				res[i + j + 1] = tmp % 10 + '0';
				carry = tmp / 10;
			}
			res[i] += carry;
		}
		auto pos = res.find_first_not_of('0');
		if (pos == string::npos)
			return "0";
		return res.substr(pos, res.length() - pos);
	}
};