題目描述

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

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

Example 2:

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

Note:

1. The length of both num1 and num2 is < 110.
2. Both num1 and num2 contain only digits 0-9.
3. Both num1 and num2 do not contain any leading zero, except the number 0 itself.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

給定兩個以字符串形式表示的非負整數(shù) num1 和 num2硼被，返回 num1 和 num2 的乘積县昂，它們的乘積也表示為字符串形式。

num1 和 num2 的長度小于110辜窑。
num1 和 num2 只包含數(shù)字 0-9茎芋。
num1 和 num2 均不以零開頭，除非是數(shù)字 0 本身。
不能使用任何標準庫的大數(shù)類型（比如 BigInteger）或直接將輸入轉(zhuǎn)換為整數(shù)來處理古戴。

題解

由于題目要求：不能將字符串轉(zhuǎn)化成大整數(shù)來處理。所以需要換一種方法矩肩，這里打算模仿2個整數(shù)的計算過程现恼，直接計算結(jié)果。

模仿自己手算整數(shù)的計算：把兩個數(shù)末尾對齊黍檩，固定一個數(shù)字a叉袍，從末尾開始，依次用數(shù)字與另個整數(shù)b的末尾開始相乘刽酱，計算進位數(shù)喳逛、余數(shù)；整數(shù)b遍歷完成后棵里，將指向a中的數(shù)字向前移動一位润文，反復(fù)計算，直到數(shù)字a遍歷完成殿怜。

值得注意的是：需要先設(shè)定一個字符串用戶存儲臨時的結(jié)果典蝌。所以，我們要明確字符串的長度头谜，設(shè)整數(shù)1骏掀、整數(shù)2長度分別為m，n柱告；那么乘法結(jié)果的最大長度為m+n截驮。兩個數(shù)字都遍歷完成后，對臨時結(jié)果從頭到尾進行遍歷际度，舍去其中為‘0’的字符葵袭。

完整代碼：

class Solution {
public:
    string multiply(string num1, string num2) {
        int size1 = num1.size(), size2 = num2.size();
        string res(size1+size2, '0');
        
        for (int i=size1-1; i>=0; --i){
            for (int j=size2-1; j>=0; --j){
                int temp = (num1[i] - '0') * (num2[j] - '0') + (res[i+j+1] - '0');
                res[i+j] += temp / 10 ;
                res[i+j+1] = temp % 10 + '0';
            }
        }
        
        for (int i=0; i< size1+size2; i++){
            if (res[i] != '0')
                return res.substr(i);
        }
        return "0";
    }
};

歡迎關(guān)注公眾號，一起學(xué)習(xí)