letcode43:字符串相乘

前言：

• 博主收集的资料New Young，连载中。
• 博主收录的问题:New Young
• 转载请标明出处：New Young

题目

letcode:https://leetcode.cn/problems/multiply-strings/description/

思路

代码

//思路：
//用每位相乘的结果存放到数组中即可
//且

void reverseString(string& s) {
    
    size_t i = 0;
    size_t j = s.size() - 1;
    for (; i < j; ++i, --j)
    {
    
        std::swap(s[i], s[j]);
    }
}
void Sum(int* arr, int begin, const string& num, const char& ch)
{
    
    //结果是不可能把数组填满的，这是隐形的说明
    //因为每个数组的启始数据头是不同的，所以用begin来开始
    int gap = 0;//进位器 
    int len = num.size();
    int i = 0;
    int j = len - 1;
    while (i < len && j >= 0)
    {
    
        int sum = (num[j] - '0') * (ch - '0') + gap;
        gap = sum / 10;
        arr[begin - i] = sum % 10;
        ++i;
        --j;
    }
    if (gap != 0)//结果位数大于len
    {
    
        arr[begin - i] = gap;
        ++i;
    }
}
class Solution {
    
public:
    string multiply(string num1, string num2) {
    
        if ((strcmp(num1.c_str(), "0") == 0)
            || (strcmp(num2.c_str(), "0") == 0))
        {
    
            string s = "0";
            return s;
        }
        size_t len1 = num1.size();
        size_t len2 = num2.size();
        size_t len = len1 + len2;
        size_t min = len1;
        if (len1 > len2)
        {
    
            min = len2;
        }

        //数组的个数取决于最短长度的string 
        int** arr = new int* [min];
        //多位数相乘的结果位数不可能大于每位数的数位之和,因此每个数组长度取len1+len2;
        for (size_t i = 0; i < min; ++i)
        {
    
            arr[i] = new int[len];
            memset(arr[i], 0, sizeof(int) * (len));//初始化空间为0
        }
        if (min == len2)
        {
    
            for (size_t i = 0; i < min; ++i)
            {
    
                Sum(arr[i], len - 1 - i, num1, num2[len2 -1- i]);
            }
        }
        else
        {
    
            for (size_t i = 0; i < min; ++i)
            {
    
                Sum(arr[i], len - 1 - i, num2, num1[len1 - 1 - i]);
            }

        }
        int gap = 0;//进位器
        int* tmp = new int[len];
        memset(tmp, 0, sizeof(int) * (len));
        for (int i = len - 1; i >= 0; --i)
        {
    
            int sum = gap;
            for (int j = 0; j < min; ++j)
            {
    
                sum += arr[j][i];
            }
            gap = sum / 10;
            tmp[i] = sum % 10;
        }
        int i = 0;
        string s;
        while (i < len)
        {
    
            if (tmp[i] != 0)
            {
    
                for (int j = i; j < len; ++j)
                {
    
                    s += tmp[j] + '0';
                }
                break;
            }
            ++i;
        }

        return s;
    }
};