字符串-43.字符串相乘-力扣(LeetCode)

白天的黑夜

发布于 2025-10-22 17:24:37

3000

代码可运行

文章被收录于专栏：leetcode题目解析和知识分享leetcode题目解析和知识分享

运行总次数：0

代码可运行

一、题目解析

1、计算乘积后，将结果也按字符串返回

2、字符串长度在[1，200]

二、算法原理

为了方便字符串计算，我们将其逆置，符合我们的计算需求，"123"将变为"321"

解法1：模拟小学列竖式计算

但还是有细节需要注意

细节1：在高位相乘时，要补上“0”

我们自己在计算时，不加0，是因为我们知道哪里是有0的，只是懒得写。但对于我们计算字符串相加时，不加0，会导致计算出错，所以要补上0

细节2：处理前导“0”

在计算123x0的时候，由于我们对字符串进行处理，所以会出现"000"这样的结果，所以需要特殊处理一下

细节3：注意计算结果的顺序

我们逆序了相乘的字符串，但我们计算的结果也是逆序的，所以我们需要对结果进行逆置

解法2：对解法1的优化

对于解法1，我们需要处理多次进位，计算123*6，123*50，123*400的时候需要处理进位，在计算和的时候也需要处理进位，这就导致了代码实现十分麻烦，所以在此基础上提出了优化

将计算完的每一位先不处理进位，将其放入到一个数组tmp中，存放的位置也很好知道，从右往左数3是第0位，2是第1位，1是第2位，对于3*6的结果18应该放在数组下标0+0处，同理6*2的结果12放在数组下标1+0处，如此操作完后我们最后最数组内存存储的值做进位计算

用ret存储字符串，记得逆置哦

个人建议第一种解法看看官方代码就行了，真要好理解好上手，还得看解法2

链接：43. 字符串相乘 - 力扣（LeetCode）

三、代码示例

解法2：

class Solution {
public:
    int tmp[399];//这里直接开399是因为最长只有200，不超过400，虽然有点浪费
    string multiply(string num1, string num2)
    {
        int m = num1.size(),n = num2.size();
        string ret;
        reverse(num1.begin(),num1.end());
        reverse(num2.begin(),num2.end());
        for(int i = 0;i<n;i++)
        {
            for(int j = 0;j<m;j++)
            {
                tmp[i+j] += (num1[j]-'0')*(num2[i]-'0');
            }
        }
        int carry = 0;
        for(int i = 0;i<m+n-1;i++)
        {
            ret += to_string((tmp[i]+carry)%10);
            carry = (tmp[i]+carry)/10;
        }
        if(carry) ret += to_string(carry);//需要对保存进位做判断，不为0则说明字符串不完整
        reverse(ret.begin(),ret.end());
        if(ret[0]=='0'&&ret[1]=='0')//前导0特判
            return "0";
        return ret;
    }
};