package com.jiucaiyuan.net.question;
/**
* @Author jiucaiyuan 2022/3/22 21:59
* @mail services@jiucaiyuan.net
*/
public class TwoStrMultiply {
/**
* v2 leeCode上学的，确实方法好
* https://leetcode-cn.com/problems/multiply-strings/solution/zi-fu-chuan-xiang-cheng-by-leetcode-solution/
*
* 方法一的做法是从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次得到的结果累加，
* 整个过程中涉及到较多字符串相加的操作。如果使用数组代替字符串存储结果，则可以减少对字符串的操作。
* 令 m 和 n 分别表示 num1和 num2的长度，并且它们均不为 0，则 num1 和 num2 的乘积的长度为
* m+n−1 或 m+n。简单证明如下：
*
* case1 如果 num1和 num2都取最小值，则 num1=10^(m−1)，num2=10^(n−1)，
* num1×num2=10^(m+n−2) ，乘积的长度为 m+n-1;
* case2 如果 num1 和 num2都取最大值，则 num1=10^m − 1, num2=10^n − 1 ，
* num1×num2 =10^(m+n) − 10^m − 10^n + 1， 乘积显然小于 10^(m+n)且大于 10^(m+n-1) ，
* 因此乘积的长度为 m+nm+n。
*
* 由于 num1 和 num2的乘积的最大长度为 m+n，因此创建长度为 m+n 的数组 ansArr 用于存储乘积。
* 对于任意 0≤i<m 和 0≤j<n，num1[i] * num2[j] 的结果位于 ansArr[i+j+1]，
* 如果 ansArr[i+j+1]≥10，则将进位部分加到 ansArr[i+j]。
* 最后，将数组 ansArr 转成字符串，如果最高位是 00 则舍弃最高位。
*
* @param num1
* @param num2
* @return
*/
public static String multiply2(String num1, String num2) {
if (num1.equals("0") || num2.equals("0")) {
return "0";
}
int m = num1.length();
int n = num2.length();
//存放结果
int[] ansArr = new int[m + n];
for (int i = m - 1; i >= 0; i--) {
int x = num1.charAt(i) - '0';
for (int j = n - 1; j >= 0; j--) {
int y = num2.charAt(j) - '0';
//num1[i] * num2[j] 的结果位于 ansArr[i+j+1]
ansArr[i + j + 1] += x * y;
}
}
//逐个检查，有大于10的，处理进位
for (int i = m + n - 1; i > 0; i--) {
ansArr[i - 1] += ansArr[i] / 10;
ansArr[i] %= 10;
}
//如果第一位是0，则舍弃
int index = ansArr[0] == 0 ? 1 : 0;
StringBuffer ans = new StringBuffer();
while (index < m + n) {
ans.append(ansArr[index]);
index++;
}
return ans.toString();
}
/**
* v1 数字太大会越界
* @param num1
* @param num2
* @return
*/
public static String multiply(String num1, String num2) {
int result = 0;
if (num1.equals("0") || num2.equals("0")) {
return String.valueOf(result);
}
char[] str1Arr = num1.toCharArray();
char[] str2Arr = num2.toCharArray();
int weight1 = 1;
for (int i = str1Arr.length - 1; i >= 0; i--) {
if(i != str1Arr.length - 1 ){
weight1 *= 10;
}
int weight2 = 1;
for (int j = str2Arr.length - 1; j >= 0; j--) {
if(j != str2Arr.length - 1 ){
weight2 *= 10;
}
int product = ((str1Arr[i] - '0') * (str2Arr[j] - '0'));
int weight = weight1 * weight2;
result += weight * (product % 10) + (product / 10) * weight * 10;
}
}
return String.valueOf(result);
}
public static void main(String[] args) {
String str2 = "123";
String str1 = "3";
System.out.println(multiply(str1, str2));
str2 = "200";
str1 = "200";
System.out.println(multiply(str1, str2));
str2 = "21";
str1 = "21";
System.out.println(multiply(str1, str2));
str2 = "210";
str1 = "210";
System.out.println(multiply(str1, str2));
str2 = "456";
str1 = "654";
System.out.println(multiply(str1, str2));
str2 = "5102381023812";
str1 = "200123123";
System.out.println(multiply(str1, str2));
System.out.println(multiply2(str1, str2));
}
}