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

C++字符串相乘(不使用任何标准库的大数类型(比如 BigInteger)也不直接将输入转换为整数)
如图:根据题目要求直接装string转换为int计算不显示,因为num1和num2的位数最大为110位,int或者long long int都实现不了,那么我们可以考虑模拟乘法运算。
C++字符串相乘(不使用任何标准库的大数类型(比如 BigInteger)也不直接将输入转换为整数)
这里可以从右往左遍历乘数,将乘数的每一位与被乘数相乘得到对应的结果,再将每次得到的结果累加,但整个过程中涉及到较多字符串相加的操作,时间复杂度会像滚雪球一样越往后越高。

如果使用数组代替字符串存储结果,则可以减少对字符串的操作。所以在这里我们考虑用一个数组去存储每一位字符串的运算,
令 m 和 n 分别表示num1和num 2的长度,并且它们均不为 0,则num 1 和 num 2的乘积的长度为m+n−1 或 m+n。
简单证明如下:
C++字符串相乘(不使用任何标准库的大数类型(比如 BigInteger)也不直接将输入转换为整数)

由于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开始读取数据,所以坐标为ij实际对应的位数是j+1和i+1i+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)也不直接将输入转换为整数)

上一篇:剑指 Offer 14- II. 剪绳子 II


下一篇:考研机试 24.N的阶乘