LeetCode - 43. Multiply Strings

简介: 43. Multiply Strings  Problem's Link  ---------------------------------------------------------------------------- Mean:  给定两个字符串,计算这两个字符串相乘的结果.

43. Multiply Strings 

Problem's Link

 ----------------------------------------------------------------------------

Mean: 

给定两个字符串,计算这两个字符串相乘的结果.

analyse:

模拟大数乘法.

Time complexity: O(N)

 

view code

/**
* -----------------------------------------------------------------
* Copyright (c) 2016 crazyacking.All rights reserved.
* -----------------------------------------------------------------
*       Author: crazyacking
*       Date  : 2016-03-06-17.13
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <windows.h>
#include <cstring>
using namespace std;
typedef long long( LL);
typedef unsigned long long( ULL);
const double eps( 1e-8);

class Solution
{
public :
    string multiply( string num1 , string num2)
    {
        reverse( num1 . begin (), num1 . end());
        reverse( num2 . begin (), num2 . end());
        string res = "0";
        int begin = 0;
        for( int i = 0; i < num2 . length(); ++ i)
        {
            string temp_res;
            str_num_multi( num1 , num2 [ i ] - '0' , temp_res);
            add( res , temp_res , begin);
            begin ++;
        }
        reverse( res . begin (), res . end());
        // delete leader zero
        while( res . size() > 0 && res [ 0 ] == '0')
        {
            res . pop_back();
        }
        if( res . size() == 0) res . push_back( char( '0'));
        return res;
    }

    void str_num_multi( string str , int num , string & res)
    {
        int carry = 0;
        for( int i = 0; i < str . length(); ++ i)
        {
            int now = num *( str [ i ] - '0') + carry;
            carry = now / 10;
            now %= 10;
            res . push_back( char( now + '0'));
        }
        if( carry)
            res . push_back( char( carry + '0'));
    }

    void add( string & res , string num , int begin)
    {
        int len = num . length (), carry = 0 , now;
        for( int i = 0; i < len; ++ i)
        {
            if( begin < res . size())
                now =( res [ begin ] - '0') +( num [ i ] - '0') + carry;
            else now = carry +( num [ i ] - '0');
            carry = now / 10;
            now %= 10;
            if( begin >= res . size())
                res . push_back( char( now + '0'));
            else
                res [ begin ] = now + '0';
            ++ begin;
        }

        while( carry)
        {
            if( begin < res . size())
                now = carry +( res [ begin ] - '0');
            else now = carry;
            carry = now / 10;
            now %= 10;
            if( begin >= res . size())
            {
                res . push_back( char( now + '0'));
            }
            else
                res [ begin ] = now + '0';
            ++ begin;
        }
    }
};

int main()
{
    string s1 , s2;
    while( cin >> s1 >> s2)
    {
        Solution solution;
        string ans = solution . multiply( s1 , s2);
        cout << ans << endl;
    }
    return 0;
}
/*

*/
目录
相关文章
|
人工智能 算法
LeetCode 1347. 制造字母异位词的最小步骤数 Minimum Number of Steps to Make Two Strings Anagram
LeetCode 1347. 制造字母异位词的最小步骤数 Minimum Number of Steps to Make Two Strings Anagram
LeetCode 415. Add Strings
给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和。
67 0
LeetCode 415. Add Strings
LeetCode 205. Isomorphic Strings
给定两个字符串 s 和 t,判断它们是否是同构的。 如果 s 中的字符可以被替换得到 t ,那么这两个字符串是同构的。 所有出现的字符都必须用另一个字符替换,同时保留字符的顺序。两个字符不能映射到同一个字符上,但字符可以映射自己本身。
57 0
LeetCode 205. Isomorphic Strings
LeetCode 43. Multiply Strings
给定两个表示为字符串形式的非负整数num1和num2,返回num1和num2的乘积,也表示为字符串形式。
52 0
LeetCode 43. Multiply Strings
|
Java 索引 Python
LeetCode 205:同构字符串 Isomorphic Strings
题目: 给定两个字符串 s 和 *t*,判断它们是否是同构的。 如果 s 中的字符可以被替换得到 *t* ,那么这两个字符串是同构的。 所有出现的字符都必须用另一个字符替换,同时保留字符的顺序。两个字符不能映射到同一个字符上,但字符可以映射自己本身。
869 0
leetcode 205. Isomorphic Strings
题目 Given two strings s and t, determine if they are isomorphic.
679 0
|
索引 Java
LeetCode 205 Isomorphic Strings(同构的字符串)(string、vector、map)(*)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50611168 翻译 给定两个字符串s和t,决定它们是否是同构的。
829 0
|
6天前
|
算法 C++
【刷题】Leetcode 1609.奇偶树
这道题是我目前做过最难的题,虽然没有一遍做出来,但是参考大佬的代码,慢慢啃的感觉的真的很好。刷题继续!!!!!!
9 0