【Leetcode】【字符串相乘】

43. 字符串相乘

 

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

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

示例 1:

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/multiply-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

对于字符串相乘，我们先需要定义字符串相加。 

public:
    string addStrings(string num1, string num2) {
//分别获取两个字符串的数组的最大下标
        int end1=num1.size()-1,end2=num2.size()-1;
//用next来存储进位
        int next=0;
//创建存储结果的字符串
        string strRet;
//只要有一个字符串中还有数据就要继续循环
        while(end1>=0 || end2>=0)
        {
//如果读取到的非空的话，就将字符串转换为数值
            int val1=end1>=0 ?num1[end1]-'0' :0;
            int val2=end2>=0 ?num2[end2]-'0' :0;
 
            int ret=val1+val2+next;
//进位最多也只是9+9，最大也仅仅是1
            next=ret>9 ? 1:0;
//可以采用insert指定在0号位置，插入一个元素，然后将我们计算过后的结果转换为字符串传入
            // strRet.insert(0,1,(ret%10)+‘0’);
//或者是使用迭代器，将迭代器的开始位置传入，然后将我们计算过后的结果转换为字符串传入
            strRet.insert(strRet.begin(),'0'+(ret%10));
//循环迭代
            --end1;
            --end2;
        }
        //处理1+9之类的情况，如果尾部为0，而十位上的读取都已经没有数据了，
        //但是还有进位的话就需要再头插1
        if(next)
        {
            strRet.insert(strRet.begin(),'1');
        }
        return strRet;
    }

 字符串相加还可以采用更加高效的尾插法

public:
    string addStrings(string num1, string num2) {
        int end1=num1.size()-1,end2=num2.size()-1;
        int next=0;
        string strRet;
        while(end1>=0 || end2>=0)
        {
            int val1=end1>=0 ?num1[end1]-'0' :0;
            int val2=end2>=0 ?num2[end2]-'0' :0;
            int ret=val1+val2+next;
            next=ret>9 ? 1:0;
 
            //尾插
            strRet+=('0'+ ret%10);
 
            --end1;
            --end2;
        }
        //如果next还有进位就需要再尾插1
        if(next==1)
        {
            strRet+='1';
        }
 
        //逆置
        reverse(strRet.begin(),strRet.end());
        return strRet;
    }

 然后编写字符串相乘的函数。字符串相乘的函数需要调用我们字符串相加的函数。

class Solution {
 
public:
    string multiply(string num1, string num2) {
//如果两个数都是0就直接返回
        if (num1 == "0" || num2 == "0") {
            return "0";
        }
//ans中存储着我们的结果
        string ans = "0";
        int m = num1.size(), n = num2.size();
//从其中一个字符串的个位开始逐个向前遍历
//这里需要注意的是字符串的个位是size()-1的位置，而不是0！！！！
        for (int i = n - 1; i >= 0; i--) {
//创建临时字符串存储我们本次相加的结果
            string curr;
//add是用来存储进位的
            int add = 0;
//我们需要判断我们所取出的这个数的位数，然后尾插0来补足位数
            for (int j = n - 1; j > i; j--) {
                curr.push_back(0);
            }
//注意在运算的时候需要-'0'
            int y = num2.at(i) - '0';
//从个位到高位遍历另外一个字符串。
            for (int j = m - 1; j >= 0; j--) {
                int x = num1.at(j) - '0';
//不要忘了加上进位
                int product = x * y + add;
//这里我们采用的是尾插，不要忘了最后要把数据反转回来
                curr.push_back(product % 10);
//计算出我们的进位
                add = product / 10;
            }
//如果两个字符串都计算完了，但是还有进位的话，我们还需要将这个进位尾插到我们的结果字符串中
            while (add != 0) {
                curr.push_back(add % 10);
                add /= 10;
            }
//由于我们采用的是尾插，也就是说高位被放在了后面，所以要反转
            reverse(curr.begin(), curr.end());
            for (auto &c : curr) {
//不要忘了将插入的每一个字符都加上'0'
                c += '0';
            }
//调用我们的字符串加法，将我们的本次计算出来的数据相加到最终的结果中
            ans = addStrings(ans, curr);
        }
        return ans;
    }
public:
    string addStrings(string num1, string num2) {
        int end1=num1.size()-1,end2=num2.size()-1;
        int next=0;
        string strRet;
        while(end1>=0 || end2>=0)
        {
            int val1=end1>=0 ?num1[end1]-'0' :0;
            int val2=end2>=0 ?num2[end2]-'0' :0;
            int ret=val1+val2+next;
            next=ret>9 ? 1:0;
 
            //尾插
            strRet+=('0'+ ret%10);
 
            --end1;
            --end2;
        }
        //如果next还有进位就需要再尾插1
        if(next==1)
        {
            strRet+='1';
        }
 
        //逆置
        reverse(strRet.begin(),strRet.end());
        return strRet;
    }
 
};