EPI

# Description:

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

nums can be negative.

## Example:

``````[1,2,3,4] * [-2,3,4] -> [-2,8,8,7,5,6]
``````

# Idea:

num1 size1, num2 size2

num1 * num2 最大 size ＝ size1 + size2

# Code:

``````#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

// 先reverse，算好再reverse回来，index好弄一些

vector<int> integerMultiply(vector<int> num1, vector<int> num2){
int size1=num1.size();
int size2=num2.size();

int sign = num1[0] * num2[0] > 0 ? 1 : -1;

num1[0] = abs(num1[0]);
num2[0] = abs(num2[0]);

reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());

vector<int> result(size1+size2, 0);

for(int i=0; i<size1; i++){
for(int j=0; j<size2; j++){
result[i+j] += num1[i] * num2[j];
result[i+j+1] += result[i+j]/10;
result[i+j] %= 10;
}
}

while(!result.empty() && result.back() == 0){
result.pop_back();
}

if (result.empty()){
return vector<int>(1,0);
}

reverse(result.begin(), result.end());
result[0] *= sign;

return result;

}

// 倒着乘，有点麻烦
vector<int> integerMultiplyBackward(vector<int> num1, vector<int> num2){
int size1=num1.size();
int size2=num2.size();

int sign = num1[0] * num2[0] > 0 ? 1 : -1;

num1[0] = abs(num1[0]);
num2[0] = abs(num2[0]);

vector<int> result(size1+size2, 0);

for(int i=size1-1; i>=0; i--){
for(int j=size2-1; j>=0; j--){
result[i+j+1] += num1[i] * num2[j];
result[i+j] += result[i+j+1]/10;
result[i+j+1] %= 10;
}
}

int i = 0;
while(i<result.size() && result[i] == 0){
i++;
}

result.erase(result.begin(), result.begin()+i);

if ( result.empty() ){
return vector<int>(1,0);
}

result[0] *= sign;
return result;

}

int main(){
vector<int> num1={-1,2,3,4,5};
// vector<int> num2={1,2,3};
vector<int> num2={0};

for(auto elem: integerMultiply(num1, num2)){
cout<<elem<<' ';
}
cout<<endl;

for(auto elem: integerMultiplyBackward(num1, num2)){
cout<<elem<<' ';
}

}
``````