[LeetCode][Java] Multiply Strings

[LeetCode][Java] Multiply Strings

題目：

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

題意：

給定兩個數字分別用字符串表示出來，返回這兩個數字的乘積，同樣用字符串表示。

注意：數字會非常大而且是非負的。

算法分析：

方法一：

直接乘會溢出，這裡可以利用java中的 BigInteger

方法二：

參考http://pisxw.com/algorithm/Multiply-Strings.html

該題需要知道，m和n位數的乘積，最終結果為m+n-1位或是m+n位(進位時)。乘法計算中可以發現，結果中第i位，應該由第一個字符串中的第1位乘以第二個字符串中的第i位，第一個字符串中的第2位乘以第二個字符串中的第i-1位，.......第一個字符串中的第i位乘以第二個字符串中的第1位,最後累加求得，最後我們取個位上的數值，然後剩下的作為進位放到下一輪循環中

AC代碼：

方法一：

import java.math.BigInteger;  //Java
public class Solution 
{
   public String multiply(String num1, String num2) 
   {
		BigInteger temp1 = new BigInteger(num1);
		BigInteger temp2 = new BigInteger(num2);
		BigInteger result = temp1.multiply(temp2);
		return result.toString();
    }
}

public class Solution 
{
    public String multiply(String num1, String num2)
    {
        if(num1==null || num2==null)
            return ;
        if(num1.charAt(0)=='0')
            return 0;
        if(num2.charAt(0)=='0')
            return 0;
        int num1length=num1.length();
        int num2length=num2.length();
        //分別對兩個開始字符串進行轉置，便於後面的下標遍歷
        num1=new StringBuilder(num1).reverse().toString();
        num2=new StringBuilder(num2).reverse().toString();
        StringBuilder res=new StringBuilder();
        int jinwei=0;
        //從低位開始計算，最後乘積的位數為m+n-1,如果進位則是m+n
        for(int i=0;i