题目:输入两个数字字符串,如“1234567890”和“987654321”,返回二者相乘的结果字符串,如本例返回为“1219326311126352690”。
来源:某500强企业面试题目
思路:从尾部到头部,对两个字串的每个数字分别相乘,并放入结果字符串相应的位置。
#include "stdio.h" #include "stdlib.h" #include "string.h" char *BigNumMultiply(const char *n1, const char *n2) { // quit if n1 or n2 is invalid if (!n1 || !n2) { return NULL; } // get length int Len1 = strlen(n1); int Len2 = strlen(n2); int Len = Len1 + Len2; // allocate result buffer char *ret = (char *)malloc(Len + 1); if (!ret) { return NULL; } memset(ret, 0, Len + 1); // multiply for (int i = Len1 - 1; i >= 0; --i) { for (int j = Len2 - 1; j >= 0; --j) { int k = i + j + 1; // multiply digit by digit ret[k] += (n1[i] - '0') * (n2[j] - '0'); // add to upper position if (ret[k] >= 10){ ret[k - 1] += ret[k] / 10; ret[k] = ret[k] % 10; } } } // handle first 0 int d = ret[0] == 0 ? 1 : 0; for (int i = 0; i < Len - d; ++i) { ret[i] = ret[i + d] + '0'; } ret[Len - d] = '