注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex43 Multiply Strings  

2015-05-23 22:41:30|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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.

这是一个手工模拟乘法的过程,先写两个函数,一个是string 和string相加,另一个是string和char相乘,有了这两个函数,string和string相乘就比较简单了。没有什么特别的难度,见代码

/* 先把string相加的写出来
* 再把string和char相乘的写出来
*/
class Solution {
public:
string multiply(string num1, string num2) {
int len1 = num1.length();
int len2 = num2.length();
if (len1 == 0 || len2 == 0)
return 0;
//遍历第二个字符串
int i;
string sum = "",a,b;
for (i = 0; i < len2; i++)
{
a = singleMulti(num1,num2[i]);
sum.push_back('0');
sum = plus(sum,a);
}
sum = removeZeros(sum);
return sum;
}
string singleMulti(string num,char s)
{
int len = num.size();
string res;
int a, b,number =0,current =0;
int i;
for (i = len-1; i >=0; i--)
{
a = num[i]-'0';
b = s - '0';
current = a*b+number;
number = current / 10;
current = current % 10;
res.push_back(current + '0');
}
if (number>0)
res.push_back(number + '0');
reverse(res.begin(), res.end());
res = removeZeros(res);
return res;
}
string removeZeros(string res)
{
int len = res.length();

int i = 0;
while ((len>1) && res[i] == '0')
{
//len = res.length();
res = res.substr(1, len - 1);
len = res.length();
}
return res;
}
string plus(string num1,string num2)
{
//这里假设num1是较长的字符串
int len1 = num1.size();
int len2 = num2.size();
string tmp;
if (len1 <= len2)
{
tmp = num1;
num1 = num2;
num2 = tmp;
}
//这个时候num1已经是较长的字符串了
len1 = num1.size();
len2 = num2.size();
int i, j;
i = len1 - 1;
j = len2 - 1;
int a, b, number = 0, current = 0;;
string res;
while (i >= 0)
{
a = num1[i] - '0';
i--;
if (j >= 0)
{
b = num2[j] - '0';
j--;
}
else
{
b = 0;
}
current = a + b + number;
number = current / 10;
current = current % 10;
res.push_back(current + '0');
}
if (number > 0)
{
res.push_back(number+'0');
}
reverse(res.begin(), res.end());
return res;
}
};


  评论这张
 
阅读(38)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017