43. Multiply Strings（重要）

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
• You should NOT use internal library such as BigInteger.

​​Subscribe​​ to see which companies asked this question

class Solution {
public:
  string multiply(string num1, string num2) {
    int m = num1.size();
    int n = num2.size();
    vector<int> res(m+n,0);
    for (int i = 0; i < m; i++){
      for (int j = 0; j < n; j++){
        res[i+j+1] += (num1[i]-'0') * (num2[j]-'0');
      }
    }
    
    int carry = 0;
    for (int i = m + n-1; i >= 0; i--){
      int tmp = res[i] + carry;
      res[i] = tmp % 10;
      carry = tmp / 10;
    }

    int i = 0;
    while (i<m+n&&res[i] == 0) i++;//注意有乘以0的情况发生

    string ret;
    for (; i < m + n; i++){
      ret += res[i] + '0';
    }
    return ret.empty() ? "0" : ret;
  }
};

几个附带的问题。

1.大数字符串相加

string addString(string num1, string num2){
  int m = num1.size();
  int n = num2.size();
  int k = max(m, n);
  vector<int> res(k + 1, 0);
  int i = m - 1, j = n - 1;
  int carry = 0;
  while (i >= 0 || j >= 0){
    int d1 = i >= 0 ? num1[i] - '0' : 0;
    int d2 = j >= 0 ? num2[j] - '0' : 0;
    int tmp = d1+ d2+ carry;
    res[k] = tmp % 10;
    carry = tmp / 10;
    i--; j--; k--;
  }
  i = 0;
  while (i <= max(m, n) && res[i] == 0) i++;
  string ret;
  if (carry) ret += carry + '0';
  for (; i <= max(m, n); i++){
    ret += res[i] + '0';
  }
  return ret.empty() ? "0" : ret;
}

2.大数字符串相减

从后向前模拟减法，计算每一位的值时，用被减数的位减去减数，再加上10，再减去借位，结果模上10就行了。

借位则是看之前的结果是否小于10，如果小于10说明借位了。

string coreSub(string num1, string num2){
  int m = num1.size() - 1;
  int n = num2.size() - 1;
  int borrow = 0;
  vector<int> res(m+1, 0);
  while (m >= 0){
    int d1 = num1[m] - '0';
    int d2 = n >= 0 ? num2[n] - '0' : 0;
    int tmp = d1 - d2 + 10 - borrow;
    res[m] = tmp % 10;
    borrow = tmp < 10 ? 1 : 0;

    m--;
    n--;
  }
  int i = 0;
  while (i < num1.size() && res[i] == 0) i++;
  string ret;
  for (; i < num1.size(); i++){
    ret += res[i] + '0';
  }
  return ret.empty() ? "0" : ret;
}

string subString(string num1, string num2){
  int m = num1.size();
  int n = num2.size();
  if (m > n){
    return coreSub(num1, num2);
  }
  else if (m < n){
    return "-"+coreSub(num2, num1);
  }
  else{
    if (num1 > num2){
      return coreSub(num1, num2);
    }
    else if (num1 < num2){
      return "-" + coreSub(num2, num1);
    }
    else{
      return "0";
    }
  }
}

测试：

cout << subString("12", "34") << endl;
  cout << subString("12345", "78") << endl;
  cout << subString("0", "0") << endl;

-22

12267

0