image.png

数学解法

还记得怎么做的乘法吗？
从右向左，对每对数字进行相乘，并且把最后的值加起来。
我们可以得到num1[i]*num2[j]的值最终会被放到[i+j,i+j+1]上
image.png
解法如下所示

  1. public String multiply(String num1, String num2) {
  2.     int m = num1.length(),n = num2.length();
  3.     int[] pos = new int[m+n];   //最终相乘的长度为m+n
  4.     for(int i= m-1;i>=0;i--){   //从后向前遍历
  5.         for(int j=n-1;j>=0;j--){
  6.             //计算相乘的值
  7.             int mul =(num1.charAt(i) - '0') * (num2.charAt(j) - '0'); 
  8.             //p1为进位所在下标 p2为个位数所在位置
  9.             int p1 = i+j,p2=i+j+1;
  10.             //加上低位的进位
  11.             int sum = mul+pos[p2];
  12.             //累加进位
  13.             pos[p1]+=sum/10;
  14.             //个位直接更新
  15.             pos[p2]=sum%10;
  16.         }
  17.     }
  18.     StringBuilder sb = new StringBuilder();
  19.     for(int p:pos)
  20.         if(!(sb.length()==0&&p==0))      ///去掉前缀0
  21.             sb.append(p);
  22.     return sb.length()==0?"0":sb.toString();
  23. }