Leetcodes Solution 43 Multiply Strings

zhuanlan.zhihu.com

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

Note:

1. The length of both num1 and num2 is < 110.
2. Both num1 and num2 contains only digits 0-9.
3. Both num1 and num2 does not contain any leading zero.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

思路1

用carry來表示滿10的進位

class Solution{public: string multiply(string num1, string num2){ string sum(num1.size() + num2.size(), 0); for(int i = num1.size() - 1; i >= 0; --i){ int carry = 0; for(int j = num2.size() - 1; j >= 0; --j){ int tmp = (sum[i + j + 1] - 0) + (num1[i] - 0) * (num2[j] - 0) + carry; sum[i+j+1] = tmp % 10 + 0; carry = tmp / 10; } sum[i] += carry; } size_t startpos = sum.find_first_not_of("0"); if(string::npos != startpos) return sum.substr(startpos); return "0"; }};

推薦閱讀：