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 415. Add Strings
给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和。
95 0
LeetCode 415. Add Strings
LeetCode 205. Isomorphic Strings
给定两个字符串 s 和 t,判断它们是否是同构的。 如果 s 中的字符可以被替换得到 t ,那么这两个字符串是同构的。 所有出现的字符都必须用另一个字符替换,同时保留字符的顺序。两个字符不能映射到同一个字符上,但字符可以映射自己本身。
79 0
LeetCode 205. Isomorphic Strings
LeetCode 43. Multiply Strings
给定两个表示为字符串形式的非负整数num1和num2,返回num1和num2的乘积,也表示为字符串形式。
74 0
LeetCode 43. Multiply Strings
|
人工智能 算法
LeetCode 1347. 制造字母异位词的最小步骤数 Minimum Number of Steps to Make Two Strings Anagram
LeetCode 1347. 制造字母异位词的最小步骤数 Minimum Number of Steps to Make Two Strings Anagram
|
Java 索引 Python
LeetCode 205:同构字符串 Isomorphic Strings
题目: 给定两个字符串 s 和 *t*,判断它们是否是同构的。 如果 s 中的字符可以被替换得到 *t* ,那么这两个字符串是同构的。 所有出现的字符都必须用另一个字符替换,同时保留字符的顺序。两个字符不能映射到同一个字符上,但字符可以映射自己本身。
891 0
leetcode 205. Isomorphic Strings
题目 Given two strings s and t, determine if they are isomorphic.
698 0
|
索引 Java
LeetCode 205 Isomorphic Strings(同构的字符串)(string、vector、map)(*)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50611168 翻译 给定两个字符串s和t,决定它们是否是同构的。
846 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行