【LeetCode】43. 字符串相乘

た入场券 2022-05-09 14:48 170阅读 0赞

**题目链接**：[https://leetcode-cn.com/problems/multiply-strings/description/][https_leetcode-cn.com_problems_multiply-strings_description]

#### 题目描述 ####

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

#### 示例 ####

输入: num1 = “2”, num2 = “3”  
输出: “6”

输入: num1 = “123”, num2 = “456”  
输出: “56088”

**说明:**

1.  num1 和 num2 的长度小于110。
2.  num1 和 num2 只包含数字 0-9。
3.  num1 和 num2均不以零开头，除非是数字 0 本身。
4.  **不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理**。

#### 解决方法 ####

模拟乘法

class Solution { 
    public:
        string multiply(string num1, string num2) { 
            if (num1=="0" || num2=="0") return "0";
            
            vector<int> vec(13000,0);  //模拟乘法
            for (int i=num1.size()-1;i>=0;i--){ 
                int add=0;//进位
                for (int j=num2.size()-1;j>=0;j--){ 
                    int temp=(num1[i]-'0')*(num2[j]-'0');
                    vec[i+j+1]+=add+temp%10;
                    add=temp/10+vec[i+j+1]/10;
                    vec[i+j+1]%=10;
                }
                vec[i]=add;
            }
            
            string result=""; //将vector中存储的结果转化成string
            int pos=0;
            for (int i=0;i<num1.size()+num2.size();i++){ 
                if (vec[i]!=0){ 
                    pos=i;
                    break;
                }
            }
    
            for (int i=pos;i<num1.size()+num2.size();i++)
                result+=vec[i]+'0';        
            return result;
        }
    };

[https_leetcode-cn.com_problems_multiply-strings_description]: https://leetcode-cn.com/problems/multiply-strings/description/