题目描述

给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

说明:

  1. num1 和 num2 的长度小于110。
  2. num1 和 num2 只包含数字 0-9
  3. num1 和 num2 均不以零开头,除非是数字 0 本身。
  4. 不能使用任何标准库的大数类型(比如 BigInteger)直接将输入转换为整数来处理

解题思路

根据数字乘法的计算规则,从一个数个位开始依次求出与另一个数的乘积并逐位相加。下面以“98”和“99”的乘法计算来说明算法思想。

  1. 首先考虑乘积的总位数,两个数相乘的最大位数为两数的位数之和,所以先申请一个结果字符串位数为4,并且每一位都初始化为‘0’
  2. 从第一个数的个位数‘8’开始,依次与“99”相乘。在乘法过程中首先初始化每一位置的进位add为0,然后计算出对应单个位的乘积mul,比如第一位8x9=72,然后取其个位与当前位置的数字以及前一位置的进位add相加得到sum,此时sum为2+0+0=2,所以结果字符串的个位数字就为‘2’。当前位置的进位add更新为mul的十位数与sum十位数之和,此时进位add为7+0=7.
  3. 计算完一次单个位置的乘法后,最后将当前乘积的前一位更新为add,具体来说8x99=792,但遍历完99后结果只记录了最后两位“92”,此时进位add为7,所以要将前一位更新为7

计算完结果后要判断输出的总位数,因为可能出现结果字符串前几位都是0的情况,找到第一位不是0的数字然后返回之后的字符串。

代码

 class Solution {
public:
string multiply(string num1, string num2) {
int l1=num1.size(),l2=num2.size();
string res(l1+l2,'');
if(l1==||l2==)
return "";
for(int i=l1-;i>=;i--){
int add=;
for(int j=l2-;j>=;j--){
int mul=(num1[i]-'')*(num2[j]-'');
int sum=res[i+j+]+add+mul%-'';
res[i+j+]=''+sum%;
add=mul/+sum/;
}
res[i]+=add;
}
for(int i=;i<l1+l2;i++)
if(res[i]!='')
return res.substr(i);
return "";
}
};

最新文章

  1. MySQL的表使用
  2. word20161214
  3. [原创]Net实现Excel导入导出到数据库(附源码)
  4. Solr学习笔记(一)
  5. vsftp虚拟用户配置
  6. Nodejs微信接口
  7. 解决:The Operation couldn&#39;t be completed.(LaunchServicesError error 0.)
  8. 【转】OSX键盘快捷键
  9. window.onerror 应用实例
  10. Socket TCP Server一个端口可以有多少个长连接?受到什么影响?linux最大文件句柄数量总结
  11. Jqgrid pager 关于“local” dataType 动态加载数据分页的研究(没好用的研究结果)
  12. CentOS7 安装Python3,开发SocketIO 客户端
  13. 01: Python基本数据类型
  14. wx小程序 使用字体
  15. win8+iis8+PHP5安装配置和Zend Optimizer安装教程
  16. quartz + spring 配置示例
  17. 【Oracle】BLOB
  18. 解决启动Distributed Transaction Coordinator服务出错的问题
  19. 自定义单选框radio样式
  20. STM32的AFIO时钟什么时候需要开启

热门文章

  1. 用git创建仓库关联本地项目,又一直上传不上去
  2. 数据绑定-绑定Servlet内置对象
  3. html/form表单常用属性认识
  4. todo 看看堆栈里的东西
  5. mybatis查询返回的对象不为null,但是属性值为null
  6. DiffUtil和LiveData使用时遇到的问题
  7. 安装Anaconda3-201812详解
  8. Win10下注册APlayer组件的正确姿势
  9. django笔记一
  10. web开发规范文档二