LeetCode 字符串相乘（造轮子）

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

示例 1:
输入: num1 = “2”, num2 = “3”
输出: “6”

示例 2:
输入: num1 = “123”, num2 = “456”
输出: “56088”

说明：
	num1 和 num2 的长度小于110。
	num1 和 num2 只包含数字 0-9。
	num1 和 num2 均不以零开头，除非是数字 0 本身。
	不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

思路分析：对这种题，既然都说不能偷懒，那就从地球诞生的原始条件开始造轮子、造杠杆。。。
首先将string与string的乘法分解为string与char的乘法和string与string的加法。

代码如下：

class Solution {
public:
	string add(string num1, string &num2){//string与string的加法
		string result = num1;
		int lengthNumOne = num1.size();
		int lengthNumTwo = num2.size();
		int lengthResult = max(lengthNumOne, lengthNumTwo);//对齐后的长度
		//首先将数位进行对齐
		if (lengthNumOne < lengthNumTwo){
			for (int i = lengthNumOne; i < lengthNumTwo; ++i){
				result = "0" + result;
			}
		}
		else {
			for (int i = lengthNumTwo; i < lengthNumOne; ++i){
				num2 = "0" + num2;
			}
		}
		//加法的核心算法,index从低位加到下标1，因为下标0可能产生进位
		for (int index = lengthResult - 1; index > 0; --index){
			result[index] += num2[index] - '0';
			if (result[index] > '9'){//产生进位
				result[index] -= 10;
				++result[index - 1];
			}
		}
		result[0] += num2[0] - '0';
		if (result[0] > '9'){//最高位产生进位
			result[0] -= 10;
			result = "1" + result;
		}
		return result;
	}
	string multiply(string num1, int num2){//string与一位int的乘法
		string result(num1.size() + 1, '0');//长度为num1.size() + 1的“000000000000000”格式串
		for (int index = result.size() - 1; index > 0; --index){
			//这里的下标比num1的下标多了1，因为上面的格式串多了一个长度
			result[index] = result[index] - '0' + (num1[index - 1] - '0') * num2;//转换为整数相乘,结果为整数
			if (result[index] > 9){//产生进位
				result[index - 1] += result[index] / 10;//进位后为整数
				result[index] = result[index] % 10 + '0';//得重新转换为字符
			}
			else {
				result[index] += '0';
			}
		}
		if (result[0] == '0'){//相乘的结果最高位未产生进位
			return string(result, 1, num1.size());//截取
		}
		else {
			return result;
		}
	}
	string multiply(string num1, string num2) {//string与string的乘法
		if (num2 == "0" || num1 == "0"){
			return "0";
		}
		string result = "";
		int lengthNum = num2.size();
		for (int index = lengthNum - 1; index >= 0; --index){
			//将num2的低位到高位，每一位乘上num1
			string tempResult = multiply(num1, num2[index] - '0');
			tempResult += string(lengthNum - index - 1, '0');//需要进行加权num2[index],尾端添加lengthNum - index - 1个零
			result = add(result, tempResult);//添加到结果
		}
		return result;
	}
};

用C++写还好，有一些常用的数据结构、算法啥的，用C造轮子、造杠杆的才是真汉子！