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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了C++字符串相乘（不使用任何标准库的大数类型（比如 BigInteger）也不直接将输入转换为整数），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1494字，纯文字阅读大概需要3分钟。

内容图文

如图：根据题目要求直接装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）也不直接将输入转换为整数）全部内容，希望文章能够帮你解决C++字符串相乘（不使用任何标准库的大数类型（比如 BigInteger）也不直接将输入转换为整数）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端