Leetcode筆記 43. 字串相乘

題目
給定兩個以字串形式表示的非負整數 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）或直接將輸入轉換爲整數來處理。

解法

1. 類似於小時候做的豎式加法，每個數做一次乘法，再相加
2. 最後進位處理，放到string中
3. 注意一個數爲0的時候

            1   2   3
            4   5   6
  ———————————————————————
            6   12  18
        5   10  15
    4   8   12
  ————————————————————————
    4  13   28  27  18
  ————————————————————————
    5   6    0   8   8

程式碼

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
class Solution {
public:
    string multiply(string num1, string num2) {
        vector<int> ans(300,0);
        int m = num1.length(),n = num2.length();
        if(m==1&&num1[0]=='0' || n==1&&num2[0]=='0'){
            string s = "0";
             return s;
        }
        for(int i=m-1;i>=0;i--){
            int index = m-1-i;
            int x = num1[i]-'0';
            for(int j=n-1;j>=0;j--)
            	//注意下標，每次往前移動一個
                ans[index+n-1-j]+=x*(num2[j]-'0');
        }
        string res;
        int c = 0;
        for(int i=0;i<m+n-1;i++){
            int data = (c+ans[i])%10;
            c = (c+ans[i])/10;
            res.push_back(data+'0');
        }
        if(c)
            res.push_back(c+'0');
        //轉置
        reverse(res.begin(), res.end());
        return res;
    }
};
int main()
{
    string num1 = "0";
    string num2 = "9999";
    Solution s;
    cout<<s.multiply(num1, num2);
    return 0;
}

今天也是愛zz的一天哦！