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:

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

这道题求两个字符串数字的相乘结果,并保存为字符串返回. 这个应该场景可能是需要处理两个非常的大的数相乘而不受int,long的约束.这道题的解法来自yavinci.两个数相乘,都是相乘后错位相加.这里把错位相加的的结果保存在一个一维数组中,然后分别计算每位上的进位.

如图

class Solution {
public:
    string multiply(string num1, string num2) {
        int m = num1.size(), n = num2.size();
        vector<int> pos(m+n,0);
        for (int i=m-1;i>=0;i--){
            for (int j=n-1;j>=0;j--){
                int mul = (num1[i]-'0')*(num2[j]-'0');
                int p1 = i+j, p2 = i+j+1;
                int sum = mul + pos[p2];
                
                pos[p1] += sum/10;
                pos[p2] = sum%10;
            }
        }
        string res = "";
        for (int i=0;i<pos.size();i++){
            if (res.size()==0&&pos[i]==0) continue;
            res += to_string(pos[i]);
        }
        return res.size()==0?"0":res;
    }
};

参考资料

https://leetcode.com/problems/multiply-strings/discuss/17605/Easiest-JAVA-Solution-with-Graph-Explanation

 
comments powered by Disqus