题目描述（中等难度）

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 哦 ^^

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