[LeetCode]大数問題,加算と乗算,問題Multiply Strings
7510 ワード
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.
私の解法はnum 2の1人を抽出するたびにnum 1に乗算し、得られた結果をstring resに組み込むことです.これにより、毎回stringを新しく定義し、効率はやや低いですが、文字列の乗算を「文字列と数字の乗算」と「文字列の加算」の2つのサブ問題に分けて、それぞれ解決すればいいという考えがはっきりしています.
処理時にnum 1とnum 2を逆順にして最低位を[0]位置にすると、処理が便利で書き間違えにくい.
Note: The numbers can be arbitrarily large and are non-negative.
class Solution {
public:
string multiply(string num1, string num2) {
}
};
私の解法はnum 2の1人を抽出するたびにnum 1に乗算し、得られた結果をstring resに組み込むことです.これにより、毎回stringを新しく定義し、効率はやや低いですが、文字列の乗算を「文字列と数字の乗算」と「文字列の加算」の2つのサブ問題に分けて、それぞれ解決すればいいという考えがはっきりしています.
処理時にnum 1とnum 2を逆順にして最低位を[0]位置にすると、処理が便利で書き間違えにくい.
class Solution {
public:
string multiply(string num1, string num2) {
if(num1.length() == 0 || num2.length() == 0)
return "";
if(num1.length() == 1 && num1[0] == '0') return "0";
if(num2.length() == 1 && num2[0] == '0') return "0";
string res(num1.length() + num2.length(), '0');
int i = 0, j = 0;
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
for(i = 0; i < num2.length(); ++i){
int offset = i;
string tmp(offset + num1.length() + 1, '0');
int add = 0;
for(j = 0; j < num1.length(); ++j){
int tmpMul = (num1[j] - '0') * (num2[i] - '0') + add;
add = tmpMul / 10;
tmp[j + offset] = (tmpMul % 10) + '0';
}
tmp[j + offset] = add + '0';
plus(res, tmp);
}
int countStartZero = 0; // '0'
for(i = res.length() - 1; i >= 0 && res[i] == '0'; --i, ++countStartZero);
if(countStartZero == res.length()) return "0";
res = res.substr(0, res.length() - countStartZero);
reverse(res.begin(), res.end());
return res;
}
private:
void plus(string &s1, string &s2){
int add = 0;
for(int i = 0; i < s1.length() && (add > 0 || i < s2.length()); ++i){
int tmp = (s1[i] - '0') + add;
if(i < s2.length()) tmp += (s2[i] - '0');
add = tmp / 10;
s1[i] = (tmp % 10) + '0';
}
}
};