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.
- Converting the input string to integer is NOT allowed.
- You should NOT use internal library such as BigInteger.
兩個 string 來做相乘的動作,基本上就是把乘法的步驟做分解
想法可以用以下圖來解釋(參考資料)
- 首先,m 位數乘上 n 位數,答案最多就是 m+n 位數
- 和一般算乘法一樣,先把每個位元相乘的結果算出來,然後根據位置相加起來
- 接著進行求餘數,進位相加的動作
- 記得要把多餘的前置0給拿掉
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
string multiply(string num1, string num2) { | |
const int len1 = num1.length(), len2 = num2.length(); | |
const int maxLen = len1 + len2; | |
int tempAns[maxLen] = {0}; | |
//> step 1 : multiply | |
int k = maxLen - 2; | |
for(int i = 0; i < len1; i++) { | |
for(int j = 0; j < len2; j++) { | |
tempAns[k - i - j] += static_cast<int>(num1[i] - '0') * static_cast<int>(num2[j] - '0'); | |
} | |
} | |
//> step 2 : calculate mod and carry | |
int carry = 0; | |
for(int i = 0; i < maxLen; i++) { | |
int quotient = (tempAns[i] + carry) / 10; | |
tempAns[i] = (tempAns[i] + carry) - 10 * quotient; | |
carry = quotient; | |
} | |
//> step 3 : removing leading zeros | |
int startIdx = maxLen - 1; | |
while(startIdx >= 0 && tempAns[startIdx] == 0) { | |
--startIdx; | |
} | |
if(startIdx < 0) { | |
return "0"; | |
} | |
//> step 4 : transform to string | |
string ans; | |
for(int i = startIdx; i >= 0; i--) { | |
ans.push_back(static_cast<char>(tempAns[i] + '0')); | |
} | |
return ans; | |
} | |
}; |
沒有留言:
張貼留言