字串相乘大數乘法

題目

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

範例 1:

輸入: num1 = 「2」, num2 = 「3」
輸出: 「6」

範例 2:

輸入: num1 = 「123」, num2 = 「456」
輸出: 「56088」

說明：

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

思路

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

一個整理樣例：

                        1   2   3
                    乘  4   5   6
                ————————————————————
                        6   12  18
                    5   10  15
                4   8   12
                ————————————————————
                4   13  28  27  18
                整理： c[i + 1] += c[i] / 10, c[i] %= 10, 從低位開始。
                step 0: 4   13  28  27  18
                step 1: 4   13  28  28  8
                step 2: 4   13  30  8   8
                step 3: 4   16  0   8   8
                step 4: 5   6   0   8   8

程式碼

class Solution {
public:
    string multiply(string num1, string num2) {
        string ans;
        vector<int> a, b, c;
        c.resize(num1.size() + num2.size() - 1);
        for (int i = num1.size() - 1; i >= 0; i--) a.push_back(num1[i] - '0');
        for (int i = num2.size() - 1; i >= 0; i--) b.push_back(num2[i] - '0');
        
        for (int i = 0; i < a.size(); i++) {
            for (int j = 0; j < b.size(); j++) {
                c[i + j] += a[i] * b[j];
            }
        }

        int k = 0;
        for (int i = 0; i < c.size(); i++) {
            k += c[i];
            char ch = k % 10 + '0';
            ans = ch + ans;
            k /= 10;
        }

        if(k){
            char ch = k % 10 + '0';
            ans = ch + ans;
        }        

        while (ans.size() > 1 && ans[0] == '0') ans.erase(ans.begin());
        return ans;
    }

};

字串相乘 大數乘法

題目

思路

程式碼