博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
LeetCode - 43. Multiply Strings
阅读量:6859 次
发布时间:2019-06-26

本文共 2381 字,大约阅读时间需要 7 分钟。

43. Multiply Strings 

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

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;
}
/*
*/

转载地址:http://grxyl.baihongyu.com/

你可能感兴趣的文章
Python笔记总结week1
查看>>
c#中使用NetCDF存储二维数据的读写操作简单应用
查看>>
linux网络相关命令使用
查看>>
java基础(二)
查看>>
记录一下:chrome上,把网页保存为文件的插件
查看>>
C#和Javascript间互转的Xxtea加解密
查看>>
BAT批处理中的字符串处理详解(字符串截取)
查看>>
智力题集锦【二】
查看>>
读 《我为什么放弃Go语言》 有感
查看>>
删除MySQL中冗余字段
查看>>
MS DOS 命令大全
查看>>
升级10.10 Yosemite 后,cocoapods 出现错误(解决方案)
查看>>
UEditor编辑器两个版本任意文件上传漏洞分析
查看>>
Redis分布式锁服务(八)
查看>>
MySQL的引入
查看>>
C++单例模式
查看>>
bower安装报错”Cannot be run with sudo”解决办法
查看>>
android平台中编写jni模块的方法(3)
查看>>
软件工程网络15结对编程1——四则运算优化
查看>>
进程、应用程序域,线程和上下文之间的关系
查看>>