C++字符串相乘（不使用任何标准库的大数类型（比如 BigInteger）也不直接将输入转换为整数）

本文主要是介绍C++字符串相乘（不使用任何标准库的大数类型（比如 BigInteger）也不直接将输入转换为整数），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

如图：根据题目要求直接装string转换为int计算不显示，因为num1和num2的位数最大为110位，int或者long long int都实现不了，那么我们可以考虑模拟乘法运算。

这里可以从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次得到的结果累加，但整个过程中涉及到较多字符串相加的操作，时间复杂度会像滚雪球一样越往后越高。

如果使用数组代替字符串存储结果，则可以减少对字符串的操作。所以在这里我们考虑用一个数组去存储每一位字符串的运算，
令 m 和 n 分别表示num1和num 2的长度，并且它们均不为 0，则num 1 和 num 2的乘积的长度为m+n−1 或 m+n。
简单证明如下：

由于num 1和 num 2的乘积的最大长度为m+n，因此创建长度为m+n 的数组res 用于存储乘积。
对于任意 0≤i<m和0≤j<n，num1[i]×num 2[j] 的结果位于res[i+j+1]，
如果res[i+j+1]≥10，则将进位部分加到res[i+j]。

注意：因为我们是倒着读取运算数据所以i+j实际是比i+j+1更高一位，同时数组都是从0开始读取数据，所以坐标为i和j实际对应的位数是j+1和i+1，i+j+2对应于存储数组res又是i+j+1位。
最后，将数组 res 转成字符串，如果最高位是 0 则舍弃最高位。

看代码：

class Solution {
public:
    string multiply(string num1, string num2) {
    if(num1=="0"||num2=="0")return "0";
    int m=num1.size(),n=num2.size();
    vector<int> res(m+n);
    for(int i=m-1;i>=0;i--){
        for(int j=n-1;j>=0;j--){
            int ans=int(num1[i]-'0')*int(num2[j]-'0');
            res[i+j+1]+=ans;
        }
    }
    for(int i=m+n-1;i>=1;i--){
         res[i-1]+=res[i]/10;
         res[i]=res[i]%10;
    }
    string s;
    for(int i=0;i<m+n;i++){
        s +=to_string(res[i]);
    }
    if(s[0]=='0')s.erase(s.begin());
    return s;
    }
};

测试用例

int main()
{
    Solution *x=new Solution;
    cout << x->multiply("123456", "445");
}

测试结果

这篇关于C++字符串相乘（不使用任何标准库的大数类型（比如 BigInteger）也不直接将输入转换为整数）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！