43. 字符串相乘

发布于:2024-05-16 ⋅ 阅读:(69) ⋅ 点赞:(0)

题目

给定两个以字符串形式表示的非负整数 num1num2,返回 num1num2 的乘积,它们的乘积也表示为字符串形式。

**注意:**不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

提示:

  • 1 <= num1.length, num2.length <= 200
  • num1num2 只能由数字组成。
  • num1num2 都不包含任何前导零,除了数字0本身。

 

普通竖式法

思路

第一种方法的主要思路就是模拟我们平时手算的计算过程,其主要步骤如下:

  • 首先我们实现一个可以两个string类型可以相加的子函数。

  • 依次将每一个乘数与被乘数的结果相加就是最终结果。

  • 关键有两点:

    • 如果做string类型的乘法?

      其实我们每次的乘法都是单位数和(单位数或者多位数)相乘,那么我们可以把乘法看作是单位数次(多位数)相加。

    • 如何在乘数与被乘数的结果后面补充合适个数的零?

      乘数倒数第n位与被乘数的结果后面补充n-1个零。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

 

AC代码

class Solution {
public:
    string multiply(string num1, string num2) {
        if ("0" == num1 || "0" == num2){
            return "0";
        }
        string ret;
        int flag = 0;
        for (int i = num2.size() - 1; i >= 0; i--)
        {
            string tmp;
            int count = num2[i] - '0';
	        for (int j = 0; j < count; j++)
			{
				tmp = StringAdd(tmp, num1);
			}
            for (int k = 0; k < flag; k++)
            {
                tmp.push_back('0');
            }
            ret = StringAdd(ret, tmp);
            flag++;
        }
        return ret;
    }
    string StringAdd(string a, string b){
        int i = a.size() - 1;
        int j = b.size() - 1;
        string ret;
        int flag = 0;
        while (i >= 0 || j >= 0){
            int num1 = 0;
            if (i >= 0)
            {
                num1 = a[i] - '0';
                i--;
            }
            int num2 = 0;
            if (j >= 0)
            {
                num2 = b[j] - '0';
                j--;
            }
            int add = num1 + num2 + flag;
            if (add > 9)
            {
                flag = 1;
                add -= 10;
            }
            else
            {
                flag = 0;
            }
            ret.push_back('0' + add);
        }      
        if (1 == flag)
        {
            ret.push_back('1');
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }    
};

 

优化竖式法

思路

如果我们先不进位,最后一起进位的话就可以用一个整形数组暂时保存计算结果

  • 这个数组应该开辟多大的空间?

    如果m = num1.size() n = num2.size()

    假设num1长度是1,num2长度是1,那么最小长度为1,即为m+n-1;最大长度为2,即为m+n。

  • 如何在数组合适的位置加上计算结果?

    通过观察不难发现,被乘数的下标为i,乘数的下标为j,它们相乘的结果应该放在数组下标为i+j+1的位置。

在这里插入图片描述

在这里插入图片描述

 

AC代码

class Solution {
public:
    string multiply(string num1, string num2) {
        if ("0" == num1 || "0" == num2)
        {
            return "0";
        }
        int sz_1 = num1.size();
        int sz_2 = num2.size();
        string ret;
        vector<int> v(sz_1+sz_2, 0);
        for (int i = num2.size() - 1; i >= 0; i--){
            int x2 = num2[i] - '0';
            for (int j = num1.size() - 1; j >= 0; j--){
                int x1 = num1[j] - '0';
                v[i+j+1] += x1 * x2;
            }
        }
        int flag = 0;
        for (int i = sz_1 + sz_2 - 1; i >= 0; i--){
            v[i] += flag;
            flag = v[i] / 10;
            v[i] %= 10;
        }
        if (v[0] != 0){
            ret.push_back('0' + v[0]);
        }
        for (int i = 1; i < sz_1 + sz_2; i++)
        {
            ret.push_back('0' + v[i]);
        }
        return ret;
    }
};