每日算法之三十四：Multiply Strings

大數相乘，分別都是用字符串表示的兩個大數，求相乘之後的結果表示。

首先我們應該考慮一下測試用例會有哪些，先准備測試用例對防御性編程會有比較大的幫助，能夠考慮一些極端情況。有以下幾種用例：

1）"0","0"

2)"0","879127346783" 其中一個是零

3)"as234","123343" 存在非法字符

4)"000000000000001234","2546" 存在零前綴，有冗余計算

大概就這麼多吧。

要想實現大數乘法，必然先實現大數相加和一個大數和一個數字相乘。這樣大數相乘就可以分割迭代計算。

下面是算法，自己寫的，可能存在冗余。

class Solution {
public:
    string subTwoString(string num1,string num2)  //大數相加
{
  string result = "";
  int i = num1.length()-1;
  int j = num2.length()-1;
  int plus = 0;//進位
  while(i>=0 && j>=0)
  {
    int temp = num1[i]-'0' + num2[j]-'0' + plus;//不能忘掉進位
    result =char(temp%10+'0')+ result;
    plus = temp/10;
    i--;j--;
  }
  if(i>=0)//一種一個沒有加完，不全結果，當然還有進位
  {
    while(i>=0)
    {
      int temp = num1[i]-'0' + plus;
        result =char(temp%10+'0')+ result;
        plus = temp/10;
        i--;
    }
  }
  if(j>=0)
  {
    while(j>=0)
    {
      int temp = num2[j]-'0' + plus;
        result =char(temp%10+'0')+ result;
        plus = temp/10;
        j--;
    } 
  }
  if(plus != 0)//最後進位不為零是要在結果頭部加上
    result = char(plus+'0')+result;
  return result;
}
string multi(string num1,int num)//大數和一位數字相乘
{
  int len = num1.length()-1;
  int plus = 0;
  string result = "";
  while(len>=0)
  {
    int temp = (num1[len] - '0') * num + plus;//plus剛開始是忘掉的，也不能寫在括號內，跟加法不同
    result = char(temp%10+'0') + result;
    plus = temp/10;
    len--;
  }
  if(plus != 0)
    result = char(plus+'0') + result;
  return result;}
string multiply(string num1, string num2) {//大數相乘
	if(num1.length() == 0 || num2.length() ==0)
		return 0;
	if(num1 == "0"|| num2 == "0")
	    return "0";
	string result = "";
	int len1 = num1.length();
	int len2 = num2.length();
	for(int i = 0;i=0;k--)
	{
		string temp = multi(num1,num2[k]-'0');
		for(int l = len2-k-1;l>0;l--)
			temp = temp + "0";
		result = subTwoString(result,temp);
	}
	return result;
    }
};

下面是另一種方法，不是按照手算乘法計算的，使用了輔助數組利用特點寫的：

思路：如果兩個大數分別為m和n位，那麼結果最多為m+n位，或者為m+n-1位（最後不存在進位）。比如123和23相乘。

0 0 3 6 9 0 2 4 6 0 0 2 7 12 9 0 2 8 2 9 下面做一下解釋，第一行是123和3相乘的結果，第二行是2和123相乘的結果。順序前移了一位。第三行是把之前的計算結果相加，第四行是從後往前

求進位，知道最開始。最後，再把他們轉化成字符串即可。

string multiply(string num1, string num2) {
		if(num1=="0" || num2=="0") return "0";
		int l1 = num1.length(), l2 = num2.length();
		int* n1 = new int[l1];
		int* n2 = new int[l2];
		int* res = new int[l1+l2];
		memset(res,0,sizeof(int)*(l1+l2));
		for(int i=0; i=0; --k){
			if(k>0) res[k-1] += res[k]/10;
			res[k] %= 10;
			ss = char(res[k]+'0')+ss;
		}
		ss = ss[0]=='0'? ss.substr(1):ss;
		//return ss.empty()?"0":ss;
		return ss;
	}