43. Multiply Strings

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

1. 常规思路

使用数组来模拟两个数相乘的计算过程，每一次计算的结果都存放到一个临时数组中，注意计算过程中的

进位问题。

public String multiply(String num1, String num2)
	{
		// 先对num1和num2的情况进行判断
		if (num1 == null || num2 == null)
			return "";
		
		// 判断num1和num2的长度
		if (num2.length() > num1.length())
		{
			// 交换
			String temp = num2;
			num2 = num1;
			num1 = temp;
		}
		
		char[] c1 = num1.toCharArray();
		char[] c2 = num2.toCharArray();
		
		int[] res = new int[c1.length+c2.length];
		int[] tmp = null;
		int k = 0;
		int carry = 0; // 进位
		// c1 * c2
		for (int i=c2.length-1, count=0; i>-1; i--, count++)
		{
			k = res.length - 1 - count;
			tmp = new int[c1.length+c2.length]; // 临时数组，记录每一次相乘的结果
			for (int j=c1.length-1; j>-1; j--)
			{
				int val = (c1[j] - '0') * (c2[i] - '0') + carry;
				if (val >= 10)
				{
					carry = val / 10; 
					val = val % 10;
				}
				else
				{
					carry = 0;  // 置零
				}
				tmp[k--] = val;
			}
			// 内部计算完后，仍然可能有进位，没有处理;如 9 * 9 = 81
			if (carry != 0)
			{
				tmp[k] = carry;
				carry = 0; // 置零
			}
			System.out.println(Arrays.toString(tmp));
			// 求出的结果相加
			add(res, tmp);
			
		}
		return print(res);
	}
	
	public int[] add(int[] val1, int[] val2)
	{
		int i = val1.length-1;
		int carry = 0;
		while (i >= 0)
		{
			int temp = val1[i] + val2[i] + carry;
			if (temp >= 10)
			{
				carry = temp / 10;
				temp = temp % 10;
			}
			else
			{
				carry = 0;
			}
			val1[i] = temp;
			i--;
		}
		return val1;
	}
	
	public String print(int[] val)
	{
		StringBuffer buffer = new StringBuffer();
		int i = 0;
		while (i<val.length && val[i] == 0)
			i++;
		
		// 如果已经到达数组末尾
		if (i == val.length)
		{
			return "0";
		}
		
		// 从前向后遍历，放入到buffer中
		while (i < val.length)
		{
			buffer.append(val[i]);
			i++;
		}
		return buffer.toString();
	}