LeetCode-中等-43-字符串相乘-迭代(C)

题目

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

示例 1:

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

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

num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

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

思路

• 这道题的思路就如同日常解乘法题一样，num1的每位数字*num2*权值，再把他们加起来即可。
• 所以这里讲一下代码中处理的一些东西：
  • 首先是进位carry，用迭代的方式处理：
    • 如果是在每次计算后就将进位加上去，那么还会影响更高位的数，更高位的数也可能进位，可能会一直进位到最高位，实现起来很麻烦。
    • 因此将进位作为一个结果，用于下一轮的计算，像是迭代一样。
  • 然后是当前计算的位置current：
    • 用tempProduct保存当前位置的乘积结果，tempProduct的十位是carry，作为下一次的进位，个位是current，作为本次乘积的新结果。
      • current在乘积计算前，表示的是当前位置的数字，计算后也是，但会变化。
  • 以及积的长度：
    • n位数*n位数，如果乘数没有0，那么长度是2n-1或2n。
      • 9*9=81，1*1=1。
    • 因此直接分配2n+1个位置即可。
    • 为了计算时方便判断当前位的值，将所有的位置都初始化成'\0'。
  • 在计算上：
    • 为了方便计算，个位是product[0]，十位是product[1]，即倒序。
    • 所以计算结束后要将其转成正序。

代码

char * multiply(char * num1, char * num2){
    int len1, len2, pos1, pos2, current, carry, tempProduct; 
    char *product, exchange;
    if(num1[0]=='0' || num2[0]=='0') return "0";    //节省脑细胞的特殊情况处理。
    for(len1=0; num1[len1]!='\0';   len1++);    //num1长度获取
    for(len2=0; num2[len2]!='\0';   len2++);    //num2长度获取
    product = (char*)malloc(sizeof(char)*(len1+len2+1));    //积的空间分配，两数相乘的长度有限
    for(pos1=0; pos1<len1+len2+1;   pos1++) product[pos1] = '\0';   //分配终止符，在后面还能作为判断是否非空的条件
    //开始计算乘积
    for(pos1=len1-1; pos1>=0;  pos1--){
        for(pos2=len2-1; pos2>=0;  pos2--){
            if(product[(len1-pos1-1) + (len2-pos2-1)] == '\0') current = 0; //当前位的值
            else current = product[(len1-pos1-1) + (len2-pos2-1)] - '0';
            if(pos2 == len2-1) carry = 0;   //前一次计算的进位
            tempProduct = (num1[pos1]-'0') * (num2[pos2]-'0') + current + carry;    //乘积
            carry = tempProduct / 10;   //本次计算的进位
            current = tempProduct % 10; //本次计算后的当前位
            product[(len1-pos1-1) + (len2-pos2-1)] = current + '0'; //值赋予
        }
        //处理每轮结束后的进位
        if(carry!=0){
            if(product[(len1-pos1-1) + (len2-pos2-1)] == '\0') current = 0;
            else current = product[(len1-pos1-1) + (len2-pos2-1)] - '0';
            tempProduct = current + carry;
            current = tempProduct % 10;
            product[(len1-pos1-1) + (len2-pos2-1)] = current + '0';
        }
    }
    for(len1=len1+len2-1; product[len1]!='\0';    len1++);    //实际结果长度计算
    for(pos1=0; pos1<len1/2;   pos1++){ //颠倒结果字符串，使其为正序
        exchange = product[pos1];
        product[pos1] = product[len1-1-pos1];
        product[len1-1-pos1] = exchange;
    }
    return product;
}