Saturday, November 22, 2014

[LeetCode] 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.

思路:

做过Plus One,Add Binary等题后,这类按位运算的题就是一个葫芦里的药了。按照最原始的按位相乘,最后移位相加的法则来计算。

      3 2 1
x       4 3
_______
      9 6 3
1 2 8 4
_______
1 3 8 0 3

注意:
1. m位的数字乘以n位的数字的结果最大为m+n位:
999*99 < 1000*100 = 100000,最多为3+2 = 5位数。
2. 先将字符串逆序便于从最低位开始计算。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1.empty() || num2.empty()) return "";
        reverse(num1.begin(),num1.end());
        reverse(num2.begin(),num2.end());
        string ret(num1.size()+num2.size(),'0');
        
        for(int j=0; j<num2.size(); j++) {
            int carry = 0;
            int val = num2[j] - '0';
            for(int i=0; i<num1.size(); i++) {
                carry += ((num1[i]-'0')*val + (ret[i+j]-'0'));
                ret[i+j] = carry%10 + '0';
                carry /= 10;
            }
            if(carry!=0) ret[num1.size()+j] = carry + '0';
        }
        reverse(ret.begin(),ret.end());
        
        int count = 0;
        while(count<ret.size()-1 && ret[count]=='0') count++;
        ret.erase(0,count);
        return ret;
    }
};

总结:

题目虽然不难。要完全写对也不容易。
1. 首先要注意num1[i] * num2[j]的结果应该加到ret[i+j]的位置上。
2. 其次要注意ln 17不能遗漏最高位的进位,由于此时ret中该位为0,所以只需要将carry转为字符即可。
3. 最容易遗漏的corner case是ln 22-24。如999*0 = 0000,此时需要去掉开始的0,但又需要保留最后一个0。

6 comments:

  1. 谢谢楼主分享。。。比较好理解的一个版本 赞一个

    ReplyDelete
  2. 真牛,没一行多余的东西!

    ReplyDelete
  3. 唉,学不来!虽然知道您的代码厉害。只能欣赏一下 :)

    ReplyDelete
  4. This comment has been removed by the author.

    ReplyDelete
  5. line 13的那个local var 您起名叫 carry 有点说不过去吧?叫个 tempResult 还差不多!让我猜了大半天,还以为是什么超级idea :)

    ReplyDelete
  6. 这个比其他的代码写的都好。尤其是carry位的设计。基本思想是被乘数一位一位地与乘数乘,而不是都一位一位地乘。赞!

    ReplyDelete