solution.md

# 字符串相乘

<p>给定两个以字符串形式表示的非负整数&nbsp;<code>num1</code>&nbsp;和&nbsp;<code>num2</code>，返回&nbsp;<code>num1</code>&nbsp;和&nbsp;<code>num2</code>&nbsp;的乘积，它们的乘积也表示为字符串形式。</p><p><strong>示例 1:</strong></p><pre><strong>输入:</strong> num1 = &quot;2&quot;, num2 = &quot;3&quot;<strong><br />输出:</strong> &quot;6&quot;</pre><p><strong>示例&nbsp;2:</strong></p><pre><strong>输入:</strong> num1 = &quot;123&quot;, num2 = &quot;456&quot;<strong><br />输出:</strong> &quot;56088&quot;</pre><p><strong>说明：</strong></p><ol>	<li><code>num1</code>&nbsp;和&nbsp;<code>num2</code>&nbsp;的长度小于110。</li>	<li><code>num1</code> 和&nbsp;<code>num2</code> 只包含数字&nbsp;<code>0-9</code>。</li>	<li><code>num1</code> 和&nbsp;<code>num2</code>&nbsp;均不以零开头，除非是数字 0 本身。</li>	<li><strong>不能使用任何标准库的大数类型（比如 BigInteger）</strong>或<strong>直接将输入转换为整数来处理</strong>。</li></ol>
<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```c
#include <bits/stdc++.h>
using namespace std;
```

### after

```c
int main()
{
    Solution sol;
    string num1 = "2", num2 = "3";
    string res;

    res = sol.multiply(num1, num2);

    cout << res;
    return 0;
}
```

## 答案

```c
class Solution
{
public:
    string multiply(string num1, string num2)
    {
        if (num1 == "0" || num2 == "0")
            return "0";
        int size1 = num1.size(), size2 = num2.size();
        string str(size1 + size2, '0');
        for (int i = size2 - 1; i >= 0; --i)
        {
            int mulflag = 0, addflag = 0;
            for (int j = size1 - 1; j >= 0; --j)
            {
                int temp1 = (num2[i] - '0') * (num1[j] - '0') + mulflag;
                mulflag = temp1 / 10;
                temp1 = temp1 % 10;
                int temp2 = str[i + j + 1] - '0' + temp1 + addflag;
                str[i + j] = temp2 % 10 + '0';
                addflag = temp2 / 10;
            }
            str[i] += mulflag + addflag;
        }
        if (str[0] == '0')
            str = str.substr(1, str.size());
        return str;
    }
};
```
## 选项


### A

```c
class Solution
{
public:
    string multiply(string num1, string num2)
    {
        string res(num1.length() + num2.length(), '0');
        for (int i = num2.length() - 1; i >= 0; i--)
        {
            int j, carry = 0;
            for (j = num1.length() - 1; j >= 0; j--)
            {
                carry += (num1[j] - '0') * (num2[i] - '0') + (res[i + j + 1] - '0');
                res[i + j + 1] = carry % 10 + '0';
                carry /= 10;
            }
            res[i + j + 1] = carry + '0';
        }
        int i;
        for (i = 0; i < res.length() - 1; i++)
        {
            if (res[i] != '0')
            {
                break;
            }
        }
        return res.substr(i);
    }
};
```

### B

```c
class Solution
{
public:
    string multiply(string num1, string num2)
    {
        if (num1 == "0" || num2 == "0")
        {
            return "0";
        }
        int n1 = num1.size(), n2 = num2.size();
        int n = n1 + n2;
        vector<int> ves(n, 0);
        int k = n - 2;
        for (int i = 0; i < n1; i++)
            for (int j = 0; j < n2; j++)
            {
                ves[k - i - j] += (num1[i] - '0') * (num2[j] - '0');
            }
        int carry = 0;
        for (int i = 0; i < n; i++)
        {
            ves[i] += carry;
            carry = ves[i] / 10;
            ves[i] %= 10;
        }

        int t = n - 1;
        while (ves[t] == 0)
        {
            --t;
        }
        string result;
        while (t >= 0)
        {
            result.append(1, ves[t] + '0');
            --t;
        }
        return result;
    }
};
```

### C

```c
class Solution
{
public:
    string multiply(string num1, string num2)
    {
        string &upper = num1;
        string &down = num2;
        deque<int> res, adv;
        for (int i = 0; i < down.length(); i++)
        {
            if (!res.empty())
            {
                for (int k = 0; k < upper.length() - 1; k++)
                {
                    adv.push_back(res.back());
                    res.pop_back();
                }
            }
            for (int j = 0; j < upper.length(); j++)
            {
                if (adv.empty())
                {
                    res.push_back(
                        (down[i] - '0') * (upper[j] - '0'));
                }
                else
                {
                    res.push_back(
                        adv.back() + (down[i] - '0') * (upper[j] - '0'));
                    adv.pop_back();
                }
            }
        }

        deque<int>::iterator it = res.end() - 1;
        while (it != res.begin() - 1)
        {
            if (*it > 9)
            {

                if (it == res.begin())
                {
                    int tmp = *it;
                    *it = tmp % 10;
                    res.push_front(tmp / 10);
                }
                else
                {
                    int tmp = *it;
                    *it = tmp % 10;
                    *(it - 1) += tmp / 10;
                }
            }
            it--;
        }
        string _r;
        for (it = res.begin(); it != res.end(); it++)
        {
            _r += (*it + '0');
        }
        return _r;
    }
};
```