题目
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
说明
1、num1 和 num2 的长度小于110。
2、num1 和 num2 只包含数字 0-9。
3、num1 和 num2 均不以零开头，除非是数字 0 本身。
4、不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
示例 1:
输入: num1 = “2”, num2 = “3”
输出: “6”
示例 2:
输入: num1 = “123”, num2 = “456”
输出: “56088”
解法一 普通竖式
乘法在实际中的运算方法如下：
其实就是71234+6123410+51234*100的和，即8638+74040+617000的和。我们按照这个规律进行累加求和即可。(num2的每一位数字与num1相乘然后补0再累加求和)
String类型如何求和？
见链接字符串相加
普通竖式代码
public class problem43 {
//多位乘法
public String multiply(String num1, String num2) {
if(num1.equals("0")||num2.equals("0")) return "0";
String res="";
//num2逐位与num1相乘
for(int i=num2.length()-1;i>=0;i--){
int carry=0;
//逐位乘的暂存结果
StringBuilder temp=new StringBuilder();
//给暂存结果补0,暂存结果暂时反序存储
for(int j=0;j<num2.length()-1-i;j++){
temp.append("0");
}
//类加结果
res=addStrings(res, singleMulti(num1, num2.charAt(i)+"", temp));
}
return res;
}
//加法
public String addStrings(String num1, String num2) {
StringBuilder res=new StringBuilder();
int carry=0;//临时和
int i=num1.length()-1;
int j=num2.length()-1;
while(i>=0||j>=0||carry!=0){
//在i、j指针未溢出时，将对应位的字符转为数字
//char本身也是由数字表示，所以它想转为int直接将本身的编码减去0的编码即可
if(i>=0) carry+=num1.charAt(i--)-'0';
if(j>=0) carry+=num2.charAt(j--)-'0';
res.append(carry%10);
carry=carry/10;
}
return res.reverse().toString();
}
//一位与多位乘法,res为额外的累加值,num1为多位数,num2为单个数
public String singleMulti(String num1,String num2,StringBuilder res){
int carry=0;
int n=Integer.parseInt(num2);
for(int j=num1.length()-1;j>=0||carry!=0;j--){
int m=j<0 ? 0:num1.charAt(j)-'0';
int product = (n*m+carry)%10;
res.append(product);
carry=(n*m+carry)/10;
}
return res.reverse().toString();
}
public static void main(String[] args) {
problem43 pro=new problem43();
System.out.println(pro.multiply("123", "45"));
}
}
解法二 优化竖式
其实我们把竖式的计算过程更加还原了，减少了加法的过程。num1与num2相乘的结果一共最多M+N位，不外乎就是每位对应相乘然后求和的过程吗，而num1[i]与num2[j]的乘法结果低位在res[i+j+1]，高位在res[i+j]。由此规律，有了以下解法。
解法二代码
public class problem43_2 {
public String multiply(String num1, String num2) {
//特判
if(num1.equals("0")||num2.equals("0")) return "0";
//结果集,每一位代表结果对应位上的值
int[] res=new int[num1.length()+num2.length()];
for(int i=num1.length()-1;i>=0;i--){
int n=num1.charAt(i)-'0';
for(int j=num2.length()-1;j>=0;j--){
int m=num2.charAt(j)-'0';
int sum=res[i+j+1]+n*m;
res[i+j+1]=sum%10;
res[i+j]+=sum/10;
}
}
//将int[]结果转为String
StringBuilder strbu=new StringBuilder();
for(int i=0;i<res.length;i++){
if(i==0&&res[0]==0) continue;
strbu.append(res[i]);
}
return strbu.toString();
}
public static void main(String[] args) {
problem43_2 pro=new problem43_2();
System.out.println(pro.multiply("999", "99"));
}
}