43. 字串相乘

題目描述

給定兩個以字串形式表示的非負整數 num1 和 num2，返回 num1 和 num2 的乘積，它們的乘積也表示爲字串形式。

樣例

範例 1:

輸入: num1 = "2", num2 = "3"
輸出: "6"

範例 2:

輸入: num1 = "123", num2 = "456"
輸出: "56088"

說明：

1. num1 和 num2 的長度小於110。
2. num1 和 num2 只包含數位 0-9。
3. num1 和 num2 均不以零開頭，除非是數位 0 本身。
4. 不能使用任何標準庫的大數型別（比如 BigInteger）或直接將輸入轉換爲整數來處理。

分析

1. 把兩個數用陣列 a, b 來儲存，並且反轉（從個位開始乘）
2. 對於 a 的第 i 位 和 b 的第 j 位相乘的結果儲存在 c[i + j] 上，即 c[i + j] += a[i] * b[j];
   這裏用加號是因爲有多種情況都會對映到 i + j 位上。
3. 最後，從 c 的低位向高位整理，c[i + 1] = c[i] / 10, c[i] %= 10;

參考程式碼

• 這個程式碼是按照比較常規的高精度乘法模板求解，考慮了新手更能理解的高精度乘法程式碼模板，如果想要更高的時間效率，可以從下標考慮進行優化
• 時間複雜度：這次沒有再每次計算一遍大整數加法，在計算num1每一位和num2每一位的乘積的時候，時間複雜度爲$O(mn)$
• 空間複雜度：所開闢的陣列儲存乘積大小$O(m+n)$

/*
 * @Author: motongxue
 * @Date: 2020-08-13 19:53:33
 * @LastEditors: motongxue
 * @LastEditTime: 2020-08-13 20:16:56
 * @Blog: https://motongxue.cn
 * @Description: file content
 */
public class multiply43 {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0"))
            return "0";
        int len1 = num1.length();
        int len2 = num2.length();
        int[] n1 = new int[len1 + 1];
        int[] n2 = new int[len2 + 1];
        int[] ans = new int[len1 + len2 + 10];
        for (int i = 0; i < len1; i++)
            n1[len1 - i] = num1.charAt(i) - '0';
        for (int i = 0; i < len2; i++)
            n2[len2 - i] = num2.charAt(i) - '0';
        for(int i=1;i<=len1;i++){		//相當於學習小學的乘法，一位數一位數相乘，然後相加起來
            for(int j=1;j<=len2;j++){
                ans[i+j-1] += n1[i]*n2[j];
                ans[i+j] += ans[i+j-1]/10;
                ans[i+j-1] %= 10;
            }
        }
        int sum = ans[len1+len2]==0?len1+len2-1:len1+len2;
        StringBuffer res = new StringBuffer();
        for(int i=sum;i>0;i--)
            res.append(ans[i]);
        return res.toString();
    }
}

提交結果