朝阳无限好 - Morning Sun Community

 找回密码
 注册
查看: 60|回复: 1

[中等] 43. 字符串相乘

[复制链接]
发表于 2020-3-29 21:32:06 | 显示全部楼层 |阅读模式
给定两个以字符串形式表示的非负整数 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
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

 楼主| 发表于 2020-3-29 21:32:33 | 显示全部楼层
  1. int plus(char *result, int resultLen, char *line, int lineLen, int size, int pos)
  2. {
  3.     int i;
  4.     int tmp = 0; /* 进位标识 */

  5.     //printf("result is ");
  6.     //for (i = resultLen - 1; i >= 0; i--) {
  7.     //    printf("%d", result[i]);
  8.     //}
  9.     //printf("\npos is %d, line is ", pos);
  10.     //for (i = lineLen - 1; i >= 0; i--) {
  11.     //    printf("%d", line[i]);
  12.     //}

  13.     for (i = pos; ((i - pos) < lineLen) || (i < resultLen); i++) {
  14.         if ((i - pos) < lineLen) {
  15.             result[i] += (line[i - pos] + tmp);
  16.         } else {
  17.             result[i] += tmp;
  18.         }
  19.         tmp = 0;
  20.         if (result[i] > 9) {
  21.             tmp = result[i] / 10;
  22.             result[i] = result[i] % 10;
  23.         }
  24.     }
  25.     if (resultLen < (lineLen + pos)) {
  26.         resultLen = lineLen + pos;
  27.     }
  28.     if (tmp) {
  29.         result[resultLen] = tmp;
  30.         resultLen += 1;
  31.     }

  32.     //printf("\n after result is ");
  33.     //for (i = resultLen - 1; i >= 0; i--) {
  34.     //    printf("%d", result[i]);
  35.     //}
  36.     //printf("\nresult len =%d\n", resultLen);

  37.     return resultLen;
  38. }

  39. char * multiply(char * num1, char * num2){
  40.     int len1 = strlen(num1);
  41.     int len2 = strlen(num2);
  42.     char *line;
  43.     char *result;
  44.     int size = len1 + len2 + 1;
  45.     int i;
  46.     int j;
  47.     int posI;
  48.     int posJ;
  49.     int tmp;
  50.     int lineLen;
  51.     int resultLen = 0;

  52.     if (!num1 || !num2) {
  53.         return NULL;
  54.     }

  55.     result = (char*)malloc(size);
  56.     line = (char*)malloc(size);
  57.     memset(result, 0, size);

  58.     if ((num1[0] == '0') || (num2[0] == '0')) {
  59.         result[0] = '0';
  60.         free(line);
  61.         return result;
  62.     }

  63.     /* i为被乘数的位数索引,从个位开始 */
  64.     for (i = 0; i < len2; i++) {
  65.         posI = len2 - 1 - i;
  66.         if (num2[posI] == '0') {
  67.             continue;
  68.         }
  69.         //printf("M is %d\n", num2[posI] - '0');
  70.         memset(line, 0, size);
  71.         /* j为乘数的位数索引,从个位开始 */
  72.         for (j = 0; j < len1; j++) {
  73.             posJ = len1 - 1 - j;
  74.             tmp = (num1[posJ] - '0') * (num2[posI] - '0');
  75.             //printf("N is %d\n", num1[posJ] - '0');
  76.             line[j] += tmp;
  77.             if (line[j] > 9) {
  78.                 line[j + 1] = line[j] / 10;
  79.                 line[j] = line[j] % 10;
  80.             }
  81.             //printf("line[j]=%d, j+1=%d\n", line[j], line[j+1]);
  82.         }
  83.         lineLen = (line[len1]) ? (len1 + 1) : (len1);
  84.         /* 每行的结果累加到result中 */
  85.         resultLen = plus(result, resultLen, line, lineLen, size, i);
  86.     }
  87.     for (i = 0; i < resultLen; i++) {
  88.         line[i] = result[resultLen - i - 1] + '0';
  89.     }
  90.     line[resultLen] = 0;
  91.     free(result);
  92.     return line;
  93. }
复制代码
执行结果:通过
显示详情

执行用时 :12 ms, 在所有 C 提交中击败了27.04%的用户
内存消耗 :5.7 MB, 在所有 C 提交中击败了100.00%的用户

回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

QQ|小黑屋|手机版|Archiver|朝阳无限好 ( 琼ICP备19005269号-1 )

GMT+8, 2020-7-7 17:31 , Processed in 0.061572 second(s), 24 queries .

快速回复 返回顶部 返回列表