2016年12月10日 星期六

[LeetCode] 43. Multiply Strings

轉自LeetCode

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.
<Solution>

兩個 string 來做相乘的動作,基本上就是把乘法的步驟做分解

想法可以用以下圖來解釋(參考資料)

  • 首先,m 位數乘上 n 位數,答案最多就是 m+n 位數
  • 和一般算乘法一樣,先把每個位元相乘的結果算出來,然後根據位置相加起來
  • 接著進行求餘數,進位相加的動作
  • 記得要把多餘的前置0給拿掉
code 如下

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;
}
};

沒有留言:

張貼留言