题目描述(中等难度)

43. Multiply Strings - 图1

就是两个数相乘,输出结果,只不过数字很大很大,都是用 String 存储的。也就是传说中的大数相乘。

解法一

我们就模仿我们在纸上做乘法的过程写出一个算法。

43. Multiply Strings - 图2

个位乘个位,得出一个数,然后个位乘十位,全部乘完以后,就再用十位乘以各个位。然后百位乘以各个位,最后将每次得出的数相加。十位的结果要补 1 个 0 ,百位的结果要补两个 0 。相加的话我们可以直接用之前的大数相加。直接看代码吧。

  1. public String multiply(String num1, String num2) {
  2. if (num1.equals("0") || num2.equals("0")) {
  3. return "0";
  4. }
  5. String ans = "0";
  6. int index = 0; //记录当前是哪一位,便于后边补 0
  7. for (int i = num2.length() - 1; i >= 0; i--) {
  8. int carry = 0; //保存进位
  9. String ans_part = ""; //直接用字符串保存每位乘出来的数
  10. int m = num2.charAt(i) - '0';
  11. //乘上每一位
  12. for (int j = num1.length() - 1; j >= 0; j--) {
  13. int n = num1.charAt(j) - '0';
  14. int mul = m * n + carry;
  15. ans_part = mul % 10 + "" + ans_part;
  16. carry = mul / 10;
  17. }
  18. if (carry > 0) {
  19. ans_part = carry + "" + ans_part;
  20. }
  21. //补 0
  22. for (int k = 0; k < index; k++) {
  23. ans_part = ans_part + "0";
  24. }
  25. index++;
  26. //和之前的结果相加
  27. ans = sumString(ans, ans_part);
  28. }
  29. return ans;
  30. }
  31. //大数相加
  32. private String sumString(String num1, String num2) {
  33. int carry = 0;
  34. int num1_index = num1.length() - 1;
  35. int num2_index = num2.length() - 1;
  36. String ans = "";
  37. while (num1_index >= 0 || num2_index >= 0) {
  38. int n1 = num1_index >= 0 ? num1.charAt(num1_index) - '0' : 0;
  39. int n2 = num2_index >= 0 ? num2.charAt(num2_index) - '0' : 0;
  40. int sum = n1 + n2 + carry;
  41. carry = sum / 10;
  42. ans = sum % 10 + "" + ans;
  43. num1_index--;
  44. num2_index--;
  45. }
  46. if (carry > 0) {
  47. ans = carry + "" + ans;
  48. }
  49. return ans;
  50. }

时间复杂度:O(m * n)。m,n 是两个字符串的长度。

空间复杂度:O(1)。

解法二

参考这里

上边的解法非常简单粗暴,但是不够优雅。我们看一下从未见过的一种竖式计算。

43. Multiply Strings - 图3

我们把进位先不算,写到对应的位置。最后再统一更新 pos 中的每一位。

而对于运算中的每个结果,可以观察出一个结论。

num1 的第 i 位乘上 num2 的第 j 位,结果会分别对应 pos 的第 i + j 位和第 i + j + 1 位。

例如图中的红色部分,num1 的第 1 位乘上 num2 的第 0 位,结果就对应 pos 的第 1 + 0 = 1 和 1 + 0 + 1 = 2 位。

有了这一点,我们就可以遍历求出每一个结果,然后更新 pos 上的值就够了。

  1. public String multiply(String num1, String num2) {
  2. if (num1.equals("0") || num2.equals("0")) {
  3. return "0";
  4. }
  5. int n1 = num1.length();
  6. int n2 = num2.length();
  7. int[] pos = new int[n1 + n2]; //保存最后的结果
  8. for (int i = n1 - 1; i >= 0; i--) {
  9. for (int j = n2 - 1; j >= 0; j--) {
  10. //相乘的结果
  11. int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
  12. //加上 pos[i+j+1] 之前已经累加的结果
  13. int sum = mul + pos[i + j + 1];
  14. //更新 pos[i + j]
  15. pos[i + j] += sum / 10;
  16. //更新 pos[i + j + 1]
  17. pos[i + j + 1] = sum % 10;
  18. }
  19. }
  20. StringBuilder sb = new StringBuilder();
  21. for (int i = 0; i < pos.length; i++) {
  22. //判断最高位是不是 0
  23. if (i == 0 && pos[i] == 0) {
  24. continue;
  25. }
  26. sb.append(pos[i]);
  27. }
  28. return sb.toString();
  29. }

时间复杂度:O(m * n)。m,n 是两个字符串的长度。

空间复杂度:O(m + n)。m,n 是两个字符串的长度。

如果按普通的思路写,这道题也不难。新的竖式的计算,让人眼前一亮,代码优雅了很多。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话,可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法,强烈推荐一个我之前学过的课程,可以点击 这里 查看详情