当前位置：首页 > article >正文

【C++】字符串相乘

article 2024/11/19 0:15:45

1.题目

2.代码

介绍一种比较简单的方法，就是先将字符串逆序，然后取出其中每一位的数相乘、相加。最后再考虑进位问题。

class Solution {
public:
    string multiply(string num1, string num2) {
        //先排除边界情况，防止输出"00000..."
        if(num1=="0"||num2=="0") return "0";
        int size1=num1.size(),size2=num2.size();
        vector<int> tem(size1+size2-1,0);
        //先将字符串逆序
        reverse(num1.begin(),num1.end());
        reverse(num2.begin(),num2.end());
        //无进位相加
        for(int i=0;i<size1;i++){
            for(int j=0;j<size2;j++){
                tem[i+j]+=(num1[i]-'0')*(num2[j]-'0');
            }
        }
        //t记录余数和进位，n防止越界。
        int t=0,n=0;
        string str;
        //处理进位问题
        while(n<size1+size2-1||t){
            if(n<size1+size2-1) t+=tem[n++];
            str+=t%10+'0';
            t=t/10;
        }
        reverse(str.begin(),str.end());
        return str;
    }
};