LeetCode: Multiply Strings

题目

https://oj.leetcode.com/problems/multiply-strings/

分析

大数乘法,不能直接相乘,因为会溢出。

首先两个乘数的各位之间两两相乘,得到多个同一列结果相加,

然后对结果进行进位。

如 25 × 25 = 625

                      2                5

     ×               2                5

————————————————————

                     10             25

          4         10

————————————————————

          4         20             25

————————————————————

          6           2              5

代码

class Solution
{
public:
    string multiply(string num1, string num2)
    {
        vector<int> temp_res(num1.size() + num2.size(), 0);
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());

        for (int i = 0; i < num1.size(); i++)
            for (int j = 0; j < num2.size(); j++)
                temp_res[i + j] += (num1[i]-'0') * (num2[j]-'0');

        int carry = 0;
        for (int i = 0; i < temp_res.size(); i++)
        {
            int temp = temp_res[i] + carry;
            temp_res[i] = temp % 10;
            carry = temp / 10;
        }

        for (int i = temp_res.size() - 1; i >= 0; i--)
        {
            if (temp_res[i] != 0)
                break;
            temp_res.pop_back();
        } 
        reverse(temp_res.begin(), temp_res.end());
        string res;
        for (int i = 0; i < temp_res.size(); i++)
            res += temp_res[i] + '0';

        return res.size() != 0 ? res : string("0");
    }
};

参考

http://www.cnblogs.com/TenosDoIt/p/3735309.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40604889