当前位置：网站首页>【LeetCode】43. 字符串相乘

【LeetCode】43. 字符串相乘

2022-07-01 15:42:00 【Uaena_An】

43. 字符串相乘

在这里插入图片描述

🧸读题

给两个字符串，相乘后得到一个字符串，这个题不能用整形做，因为后面的测试用例会很大，整形，长整形都装不行！

🧸思路

要按位相乘，存进字符串，再将乘积的得到的字符串相加，最终结果再依次存进字符串内，
在这里插入图片描述

🧸代码

class Solution {
    
public:
string addStrings(string& count, string& sum)
{
    
    //end1，end2从两数尾部相加，carry记录进位
    int end1 = count.size() - 1, end2 = sum.size() - 1, carry = 0;
    string ret;//记录两数相加的和
    while (end1 >= 0 || end2 >= 0)
    {
    
        //如果end1大于0 则说明count还有为数，则x1取end1位的值，否则取0
        int x1 = 0;
        if (end1 >= 0)
        {
    
            x1 = count[end1] - '0';
            --end1;
        }
        int x2 = 0;
        if (end2 >= 0)
        {
    
            x2 = sum[end2] - '0';
            --end2;
        }

        //add记录两数相加的和 ，加上进位，第一次进位是0
        int add = x1 + x2 + carry;
        //如果add大于9，则说明需要进位，并且add要减去10
        //并且进位置1 ，否则进位置0，不然的话进位会保留上次进位的结果，会出现错误
        if (add > 9)
        {
    
            carry = 1;
            add -= 10;
        }
        else {
    
            carry = 0;
        }
        //将进位所剩的字符尾插到 ret中，后面再翻转，以提高效率
        ret += add;
    }
    //走到这，说明两数都已经加完了，但是进位还有1位，要尾插进去
    if (carry != 0)
    {
    
        ret += carry;
        carry = 0;
    }
    //翻转
    reverse(ret.begin(), ret.end());
	//转成数字字符
	for (auto& e : ret)
	{
    
		e += '0';
	}
    return ret;
}
string multiply(string num1, string num2) {
    
    if (num1 == "0" || num2 == "0")
    {
    
        return "0";
    }
    string count = "0";//记录总和
    int end1 = num1.size() - 1, end2 = num2.size() - 1;
    //按位相乘，num2每一位 * num1所有位
    for (int i = end2; i >= 0; --i)
    {
    
        string sum;//记录乘积
        int carry = 0;//记录进位
        //当j = i时 ，说明j在各位。是最后一位相乘，不需要+0
        //当j--后 j在十位上，十位上的数乘其他数，直接在后面+1个0，以此类推
        for (int j = end2; j > i; --j)
        {
    
            sum.push_back(0);
        }
        //i控制的是num2倒叙遍历的每一位
        int x2 = num2[i] - '0';
        //下面是用x2 * num1每一位
        for (int j = end1; j >= 0; --j)
        {
    
            int x1 = num1[j] - '0';
            int ret = x1 * x2 + carry;//两数相乘+进位
            sum += ret % 10;//sum存个位 ，尾插
            carry = ret / 10;//carry存十位
        }
        //当两数乘完 进位还有数字，则需要将 进位尾插
        while (carry != 0) {
    
            sum += carry % 10;
            carry /= 10;
        }
        //尾插后 翻转字符串
        reverse(sum.begin(), sum.end());
        //将字符串转化成数字形式的字符串
        for (auto &e : sum) {
    
            e += '0';
        }
        count = addStrings(count, sum);
    }
    return count;
}
};