43. 字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

提示：

• 1 <= num1.length, num2.length <= 200
• num1 和 num2 只能由数字组成。
• num1 和 num2 都不包含任何前导零，除了数字0本身。

1、解题前置知识

1、两个长度分别为 n 和 m 的数相乘，长度不会超过 n + m。

2、我们要使用ASIC码来进行相加

• eg：int data2 = num2.charAt(j)-'0'
• ‘0’是48依次往后

3、用/来进行判断进位个数

4、用%来取余留下剩下的数

2、解题思路

1、我们直接进行模拟乘法计算

2、我们用一个数组res来存储两数相乘的结果

3、乘完后得到一个一维数组，我们再进行统一的处理

4、用1个for循环，来处理进位和保留个数位

5、用StringBuilder来进行计算和去除前置0

3、代码实现

package org.letcode;

import java.util.Arrays;

public class Num43 {

    public static void main(String[] args) {
        Num43 num43 = new Num43();
        System.out.println(num43.multiply3("123","456"));

    }

    public String multiply3(String num1, String num2) {//做乘法,时间复杂度O(len1*len2)
        if(num1.equals("0") || num2.equals("0")) return "0";
        int len1 = num1.length();
        int len2 = num2.length();
        int[] res = new int[len1+len2];//分别取最小值最大值可以证明,num1*num2的结果长度为 len1+len2-1 或 len1+len2
        Arrays.fill(res,0);
        for(int i=len1-1;i>=0;i--){
            int data1 = num1.charAt(i)-'0';
            for(int j=len2-1;j>=0;j--){
                int data2 = num2.charAt(j)-'0';
                //data1*data2的结果保留在i+j+1位置上,为什么?以i=len1-1,j=len2-1都是最低位为例,结果也应该在最低位len1+len2-1
                res[i+j+1] += data1*data2;//先不管进位,后面再统一处理
            }
        }
        for (int i = len1+len2-1; i > 0; i--) {
            if(res[i]>9){//某位上数字大于等于10了需要进位
                res[i-1] += res[i]/10; //前一个数加进位
                res[i] %= 10; //当前位只保留个位数
            }
        }
        StringBuilder sb = new StringBuilder();
        if(res[0]!=0) sb.append(res[0]);//只有最高位为不0才保留到结果中
        for(int i=1;i<len1+len2;i++){
            sb.append(res[i]);
        }
        return sb.toString();
    }

}

4、补充

1、String转Integer

1、Integer.parseInt() 或 Integer.valueOf() 将 String 转换为 int。

2、实例（Integer.parseInt()）

String number = "-7";

  // result = -7
  int result = Integer.parseInt(number);
  // result2 = -7
  Integer result2 = Integer.valueOf(number);

3、实例（ Integer.valueOf()）

String number = "123";
Integer result = Integer.valueOf(number);

2、Integer转String

1、String s = String.valueOf(i);

• 例子

• int a = 97;
  String s1 = String.valueOf(a);

2、String s = Integer.toString(i);

• 例子

• int a = 97;
  String s2 = Integer.toString(a);

3、String s = "" + i;

• 例子

• int a = 97;
  String s3 = ""+a;