每周一道算法题(三十四)

本周题目难度‘Medium'，使用语言'C'

题目：本次的题目挺有意思的，就是给你两个低于110位的数(以字符串形式给你)，让你求积后以字符串形式返回结果。

思路：这个题的思路很简单，就是实现起来会有很多坑。方法有很多种，我的思路是将两个数的每一位相乘，然后求和，最后处理下数位的问题即可，当然之间涉及到很多类型转换的问题。具体的还是看代码吧：

char* multiply(char* num1, char* num2) {
    //确定长度
    int len1 = strlen(num1);
    int len2 = strlen(num2);
    //如果有一个是0，直接返回0
    if (len1 == 1 && num1[0] == '0') return "0";
    if (len2 == 1 && num2[0] == '0') return "0";
    //创建容器并初始化
    char* result = malloc(sizeof(char) * (len1 + len2 + 1));
    for (int i = 0; i < (len1+len2); i++) {
        result[i] = '0';
    }
    result[(len1+len2)] = '\0';
    
    for (int i = 0; i < len1; i++) {
        for (int j = 0; j < len2; j++) {
            //用num1的每一位去乘以num2
            int tempNum = (num1[i] - '0') * (num2[j] - '0');   
            //确定是第几位
            int index =  i + j + 1;
            //求和
            int lowCount = (result[index] - '0') + (tempNum % 10);
            result[index] = lowCount % 10 + '0'; 
            //是否需要进位
            if (lowCount > 9 || tempNum > 9) {  
                int temp = tempNum > 9 ? (result[index - 1] - '0') + (tempNum / 10) : (result[index-1] - '0');
                lowCount = lowCount > 9 ? temp + 1 : temp;
                result[index-1] = lowCount % 10 + '0';
                int addOne = 2;
                //大于10就循环进位
                while (lowCount > 9) {
                    lowCount = (result[index-addOne] - '0') + 1;
                    result[index - addOne] = (lowCount % 10 + '0');
                    addOne++;
                }
            }
        }
    }
    //位数处理
    if (result[0] == '0') {
        for (int i = 0; i < (len1+len2); i++) {
            result[i] = result[i+1];
        }
    }
    //返回结果
    return result;
}

效率一般，还有的思路是8位数8位数相乘，这样并不会越界，可以提高效率，有兴趣的小伙伴也可以尝试一下。

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!