(LeetCode OJ) 43. Multiply Strings

43. Multiply Strings

<a class="pull-right btn btn-default" href="https://leetcode.com/problems/multiply-strings/submissions/" target="_blank">My Submissions</a><button class="btn btn-default active" type="button">Question</button>Total Accepted:51859Total Submissions:231017Difficulty:Medium

以字符串的形式給定兩個數字，返回相乘的結果，注意：結果也是字符串，因為數字可能很大

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.

Subscribeto see which companies asked this question

分析：

代碼注釋已經很詳細，模擬手算即可

//思路首先:
//模擬手算過程即可
class Solution {
public:
    string multiply(string num1, string num2) {
        int allLen=num1.size()+num2.size();
        vector tmpresult(allLen,0);
        string result(allLen,'0');
        //模擬手算從最後一位開始處理
        for(int i=num1.size()-1;i>=0;i--)
        {
            int n1=num1[i]-'0';
            for(int j=num2.size()-1;j>=0;j--)
            {
                int n2=num2[j]-'0';
                tmpresult[i+j+1]+= n1*n2;
            }
        }
        //進位
        for(int i=allLen-1;i>0;i--)
        {
            while(tmpresult[i]>9)
            {
                tmpresult[i-1]+=tmpresult[i]/10;
                tmpresult[i]%=10;
            }
        }
        //轉換成字符串
        for(int i=allLen-1;i>=0;i--)
            result[i]=tmpresult[i]+'0';
            
        if(result.find_first_not_of('0') == string::npos) 
            return "0";//排除全0的情況
        return result.substr(result.find_first_not_of('0'),string::npos);
    }
};