題目描述

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
以字符串的形式給出兩個(gè)非負(fù)的整數(shù)num1和num2瘸洛，返回兩個(gè)數(shù)的乘積亚铁，結(jié)果同樣以字符串的形式表示。

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都只包含數(shù)字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.
禁止使用內(nèi)置的BigInteger庫或者直接把輸入轉(zhuǎn)化為整數(shù)榕吼。

思路分析

禁止使用內(nèi)置的BigInteger庫或者直接把輸入轉(zhuǎn)化為整數(shù)轧邪。這句話意味著不能投機(jī)取巧直接算出來拖吼，而是要自己手動(dòng)實(shí)現(xiàn)人腦版的十進(jìn)制的乘法鼻疮。（這道題做的我都忘了乘法怎么算了假勿。借嗽。。）
十進(jìn)制的乘法就是從個(gè)位開始依次向上運(yùn)算废登，將結(jié)果的個(gè)位存入相應(yīng)位置（如果原來位置有數(shù)就相加）淹魄，如果有進(jìn)位就記錄進(jìn)位，然后再進(jìn)入下一個(gè)位置的運(yùn)算堡距。

運(yùn)算的過程

重點(diǎn)在于縷清楚乘法運(yùn)算的進(jìn)位邏輯，兩位相乘的結(jié)果個(gè)位數(shù)應(yīng)該放入res字符串的哪一位瘾英。

代碼實(shí)現(xiàn)

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();
    }

}