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;
}

You may also like...

1 Response

  1. What’s up to every one, it’s genuinely a nice for me to visit this web page, it includes useful Information.

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注