43. 字符串相乘

题目

• 题号：43
• 难度：中等
• https://leetcode-cn.com/problems/multiply-strings/

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

实现

思路1 列竖式

将列竖式计算乘法的思路按步骤编程实现出来即可。
首先我们知道当乘数nums1位数为m，被乘数nums2位数为n时，相乘的结果res最大位数为m+n，所以我们可以维护一个m+n的数组，来保存res每次更新的结果。
此外还需要观察：乘数中的某一位与被乘数中的某一位相乘时，将在res数组的哪个位置修改更新对应结果。这里可以在稿纸上画一画，最后可以看出来nums[i] x nums2[j]的结果tmp有两位，个位数位于res[i+j+1],十位数位于res[i+j]。若只有一位数则可以将十位数设为0。
（要注意res数组左边存放的是数字更大的位，右边存放的是数字更小的位，才是上面的这个关系，下面引用网上的一张图）

class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1 == "0" || num2 == "0") {
            return "0";
        }
        auto res = vector<int>(num1.size()+num2.size());
        for (int i = num1.size()-1; i>=0; i--) {
            int n1 = num1.at(i) - '0'; //转数字
            for (int j = num2.size()-1; j>=0; j--) {
                int n2 = num2.at(j) - '0';
                // 将结果加到对应位数上
                res[i+j+1] += n1*n2;
                // 如果大于10则进位
                res[i+j] += res[i+j+1] / 10;  
                res[i+j+1] = res[i+j+1] % 10;
            }
        }
        string ans;
        for( int i=0; i<res.size(); i++) {
            if(i==0 && res[i]==0) continue;  // 如果首位不为零
            ans.push_back(res[i]); 
        }
        // 转换为字符
        for (auto &c: ans) {
            c += '0';
        }
        return ans;
    }
};