题目描述

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
以字符串的形式给出两个非负的整数num1和num2，返回两个数的乘积，结果同样以字符串的形式表示。

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Note:

The length of both num1 and num2 is < 110.
num1和num2的长度都小于110
Both num1 and num2 contain only digits 0-9.
num1和num2都只包含数字0-9
Both num1 and num2 do not contain any leading zero, except the number 0 itself.
num1和num2都不含前置的0，除非本身就是0
You must not use any built-in BigInteger library or convert the inputs to integer directly.
禁止使用内置的BigInteger库或者直接把输入转化为整数。

思路分析

禁止使用内置的BigInteger库或者直接把输入转化为整数。这句话意味着不能投机取巧直接算出来，而是要自己手动实现人脑版的十进制的乘法。（这道题做的我都忘了乘法怎么算了。。。）
十进制的乘法就是从个位开始依次向上运算，将结果的个位存入相应位置（如果原来位置有数就相加），如果有进位就记录进位，然后再进入下一个位置的运算。

运算的过程
如图所示，两层循环遍历num1和num2，使得每一位相乘，乘积（例如9 * 9 = 81）的个位（1）放入res的相应位置，用carry记录进位（8），下次再计算乘积后，需要将乘积与进位carry相加，如果字符串该位置有数，则再加上该位置的数。
如图，一次循环以后，res字符串为1998（为了方便res字符串采用逆序）；
两次后，res字符串为10989；
三次后，res字符串为100899；
最后翻转res。

重点在于缕清楚乘法运算的进位逻辑，两位相乘的结果个位数应该放入res字符串的哪一位。

代码实现

public class Solution {

    /**
     * 311 / 311 test cases passed.
     *  Status: Accepted
     *  Runtime: 37 ms
     *
     * @param num1
     * @param num2
     * @return
     */
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        StringBuilder res = new StringBuilder(num1.length() + num2.length());
        int max_len = num1.length() + num2.length();
        int carry = 0;
        for (int i = num2.length() - 1; i >= 0; i--) {
            for (int j = num1.length() - 1; j >= 0; j--) {
                int tmp = (num2.charAt(i) - '0') * (num1.charAt(j) - '0');
                tmp = tmp + carry;
                if (res.length() <= max_len - i - j - 2) {
                    res.append((char) ('0' + tmp % 10));
                } else {
                    int cur = res.charAt(max_len - i - j - 2) - '0';
                    tmp += cur;
                    res.setCharAt(max_len - i - j - 2, (char) ('0' + tmp % 10));
                }
                carry = tmp / 10;
            }
            if (carry != 0) {
                res.append((char) ('0' + carry));
                carry = 0;
            }
        }
        return res.reverse().toString();
    }

    public String multiply2(String num1, String num2) {
        if(num1 == null || num2 == null || num1.length()==0 || num2.length()==0)
            return "";
        if(num1.charAt(0)=='0')
            return "0";
        if(num2.charAt(0)=='0')
            return "0";
        StringBuilder res = new StringBuilder();
        int num = 0;
        for(int i=num1.length()+num2.length();i>0;i--)
        {
            for(int j=Math.min(i-1,num1.length());j>0;j--)
            {
                if(i-j<=num2.length())
                {
                    num += (int)(num1.charAt(j-1)-'0')*(int)(num2.charAt(i-1-j)-'0');
                }
            }
            if(i!=1 || num>0)
                res.append(num%10);
            num = num/10;
        }
        return res.reverse().toString();
    }

}