力扣#43 字符串相乘（C++）

题目如下：官网oj

  题目意思就是让我们自己去模拟乘法，因为两个相乘的数字很大，long long类型都存储不下，只能拿字符串模拟乘法的过程得到答案。
  算法简述：首先考虑特殊情况，当num1或者num2为0的时候，返回0。考虑特殊情况之后把num1和num2反转过来，令num1[0]即num1的低位的位权最低，num1[num1.length()-1]即num1的高位的位权最高，这样方便我们计算求解。我们在做乘法的时候，比如1234 * 567的时候，将567的每一位与1234相乘之后，再错位相加得到答案。如下图 1234 * 567 ：

利用上述思想，可以编写两层for循环来模拟，接下来要考虑进位问题，当相乘的结果大于10就会产生进位，进到下一位，定义一个int变量carry来存放上述进位信息，容易得到这样的代码:

int tmp = (num1[i] - '0') * (num2[j] - '0') + carry+ans[i+j]-'0';
carry = tmp / 10;
ans[i + j] = tmp % 10+'0';

在固定一次b与a进行一次乘法之后，还可能产生进位，此时已经跳出了b的循环，这时候的进位应进到相应的位上，而不能丢弃，如下：

if (carry) {
		ans[i + num2.length()] += carry;
		carry = 0;
}

所有的计算结束之后，我们还需要把答案reverse一下，因为我们一开始把num1和num2都reverse了，还记得嘛。要reverse，就需要传入开头和结尾的迭代器，这时候就需要计算得到的答案的长度，具体代码见如下代码：

class Solution {
public:
    string multiply(string num1, string num2) {
    	//考虑特殊情况
        if(num1=="0"||num2=="0")
            return string("0");

		//ans长度230肯定够了
        string ans(230, '0');
        //反转数字
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());

        int carry = 0, len = num1.length() + num2.length() - 1;
        //模拟乘法
        for (int i = 0; i < num1.length(); i++) {
            for (int j = 0; j < num2.length(); j++) {
                int tmp = (num1[i] - '0') * (num2[j] - '0') + carry+ans[i+j]-'0';
                //进位
                carry = tmp / 10;
                ans[i + j] = tmp % 10+'0';
            }
            if (carry) {
            	//b的一位和a的最高位相乘还有进位，特殊处理一下
                ans[i + num2.length()] += carry;
                carry = 0;
                //整个答案的最高位还有进位，那么ans的长度加1
                if (i == num1.length() - 1)
                    len++;
            }
        }
        //反转ans
        reverse(ans.begin(), ans.begin() + len);
        //返回子串也就是最终答案
        return ans.substr(0, len);
    }
};