leetcode——腾讯企业真题--数组与字符串 11.字符串相乘

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

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

 看到这个题目第一反应是包装类，但是最后成绩的数据结果远超int，也超过了long，显然不可取

class Solution {
    public String multiply(String num1, String num2) {
    	Integer a = Integer.valueOf(num1);
    	Integer b = Integer.valueOf(num2);
    	int result = a * b;
    	return result + "";
    }
}

下面介绍模拟竖式乘法的方法思路：  

首先可以做一个判断，（0 * 任何数都是0），所以两个数中只要有一个数为0就返回"0"

定义一个StringBuider

两个非零正整数相乘的结果的长度，要么等于num1.length() + num2.length()，要么等于num1.length() + num2.length() - 1，定义数组肯定要以长的为标准。

乘法运算的规则是从第二个数字的最低位开始依次乘第一个数字的从低到高的各个位，以此类推

低位数字的低位部分先存，低位数字的高位部分进到高位。最后得到sum数组

如123 * 123 = 15129

sum 中的值依次是 0 1 4 10 12 9

取sum每个值的低位部分，利用数学规律，sum每个值的高位部分往高位进一位

如9直接添加

12先添加2，1向前进位，前面就成了11

11先添加1，1向前进位，前面就成了5

5直接添加

1直接添加

0直接添加

最后的顺序就是921510

我们发现sum的第一位是0的话会影响输出的结果，所以在遍历添加元素的时候不添加这种情况，即遇到的时候直接跳过

最后的顺序就是92151，利用StringBuider进行反序即可得到15129

最后进行反序即可。

代码：

class Solution01 {
	public String multiply(String num1, String num2) {
		if (num1.equals("0") || num2.equals("0")) {
			return "0";
		}
		StringBuilder str = new StringBuilder();
 
		int[] sum = new int[num1.length() + num2.length()];
		
		for(int i = num2.length() - 1; i >= 0; i--) {
			int x = num2.charAt(i) - '0';
			//注意charAt取得是一个数字的字节形式，减去'0'，再自动类型转换就可以得到里面的数字
			for(int j = num1.length() - 1; j >= 0; j--) {
				int y = num1.charAt(j) - '0';
				int a = x * y;
				sum[i + j + 1] += a % 10;//低位存低位的低位部分 
				sum[i + j] += a / 10;//将低位的高位部分 先加到 高一个位上
				//如12，sum[i + j + 1] += 2，sum[i + j] += 1 
			}
		}
		
		int a = 0;
		for (int i = sum.length - 1; i >= 0; i--) {
			a = sum[i] + a;
			if ((i == 0) && a == 0) {// sum的第一位为0会影响结果（结果的第一位为0）
				continue;
			}
			str.append(a % 10);//添加sum每个值的低位部分
			a = a / 10;//sum每个值的高位部分往高位进一位
		}
		return str.reverse().toString();
	}
}