首页 > 其他 > 详细

Multiply Strings

时间:2016-02-25 13:40:03      阅读:261      评论:0      收藏:0      [点我收藏+]

题目:

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.

 

class Solution {
public:
    string addTwoString(string nums1, string nums2) {

        int n1 = nums1.size();
        int n2 = nums2.size();

        if (n1 < n2)
            return addTwoString(nums2, nums1);

        int minlen = n2;
        int maxlen = n1;
        string result;
        int carry = 0;
        for (int i = 0; i < minlen; i++) {
            int sum = nums1[--n1] - ‘0‘ + nums2[--n2] - ‘0‘ + carry;
            carry = sum / 10;
            int a = sum % 10;
            result.push_back(a + ‘0‘);
        }
        for (int i = minlen; i < maxlen; i++) {
            int sum = nums1[--n1] - ‘0‘ + carry;
            carry = sum / 10;
            int a = sum % 10;
            result.push_back(a + ‘0‘);
        }

        if (carry != 0)
            result.push_back(carry + ‘0‘);
        reverse(result.begin(), result.end());

        return result;
    }

    string multiply(string nums1, string nums2) {
        string result = "0";
        if(nums1 == "0" || nums2 == "0") return result;
        vector<string> tmpResult;
        int n1 = nums1.size();
        int n2 = nums2.size();

        int carry = 0;
        reverse(nums1.begin(),nums1.end());
        reverse(nums2.begin(),nums2.end());

        for (int i = 0; i < n1; i++) {
            string str;
            for (int j = 0; j < n2; j++) {
                int sum = (nums1[i] - ‘0‘) * (nums2[j] - ‘0‘) + carry;
                carry = sum / 10;
                int a = sum - carry * 10;
                str.push_back(a + ‘0‘);
            }
            if (carry != 0)
                str.push_back(carry+‘0‘);
            carry = 0;
            reverse(str.begin(), str.end());
            for (int k = 0; k < i; k++) {
                str.push_back(‘0‘);
            }
            tmpResult.push_back(str);
        }

        int size = tmpResult.size();

        for (int i = 0; i < size; i++) {
            result = addTwoString(result, tmpResult[i]);
        }
        return result;
    }
};

 

 

Multiply Strings

原文:http://www.cnblogs.com/wxquare/p/5216465.html

踩
(0)
赞
(0)
   
举报
评论 一句话评论(0)
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!