【leetcode刷题笔记】Multiply Strings
2024-10-20 08:02:16
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.
题解:就是让实现一个大整数乘法。
假设两个数num1和num2的长度分别是len1和len2,那么最后得到的答案,在最高位有进位的时候,就是len1+len2位,否则是len1+len2-1位。我们用数组numbers[len1+len2]存放最后的结果。
很关键的一点就是在做每位之间的乘法的时候不要处理进位,在做加法的时候同一处理进位。
举个例子,12*16,我们从最低位开始相乘:
num1[i]和num2[j]对应的数相乘的积在numbers数组中存放的位置是numbers[i+j+1]。
两个数相乘最高位的进位存放在numbers[0]中,在把字符数组转换成数字的时候要单独处理;另外下面的代码中29~32行是为了避免结果出现类似“0000”这种情况,这时应该返回结果0。
代码如下:
public class Solution {
public String multiply(String num1, String num2) {
if(num1 == null || num2 == null)
return null;
int len1 = num1.length();
int len2 = num2.length();
int len3 = len1 + len2;
int[] numbers = new int[len3]; int i,j; for(i = len1-1;i >= 0;i--){
for(j=len2-1;j >= 0;j--){
numbers[i+j+1] += (num1.charAt(i)-'0') * (num2.charAt(j)-'0');
}
} int carries = 0;
for(i = len3-1;i >=0;i--){
numbers[i] += carries;
carries = numbers[i]/10;
numbers[i] %= 10;
} StringBuffer sBuffer = new StringBuffer();
sBuffer.append(numbers[0]==0?"":numbers[0]);
i = 1;
if(sBuffer.length() == 0){
while(i < len3 && numbers[i]== 0)
i++;
}
for(;i <len3;i++)
sBuffer.append(numbers[i]);
if(sBuffer.length() == 0)
sBuffer.append(0);
return sBuffer.toString();
}
}
最新文章
- ORA-00942:table or view does not exist
- Git下载Spring项目源码并编译为Eclipse
- 自定义Encoder/Decoder进行对象传递
- laravel速记(笔记)
- How to install Python 2.7 and Python 3.3 on CentOS 6
- UVA1218--树形DP
- 从零开始学 iOS 开发的15条建议
- 树形dp专辑
- java.net.BindException: Cannot assign requested address: bind
- PPPoE拨号流程
- bzoj3198[Sdoi2013]spring 容斥+hash
- vue的项目结构记录
- DBlink 创建 删除 脚本
- X分钟速成Python
- 自整理的jquery.Validate验证表达式
- Eclipse Ctrl + H 搜索文件不覆盖已打开文件解决办法
- PLSQL Developer个性化设置
- 洛谷P3538 [POI2012]OKR-A Horrible Poem [字符串hash]
- checkboxlist 横向显示,自动换行
- CERC2017 Gambling Guide,最短路变形,期望dp
热门文章
- php 佛祖保佑 永无bug
- printf,sprintf,vsprintf
- TCP和UDP 协议发送数据包的大小
- Retrofit学习笔记(一)
- 40、DrawerLayout使用详情
- HTML5新增的语义标签和IE版本低的兼容性问题
- VMware下安装centos6.7的步骤
- SharePoint服务器端对象模型 之 对象模型概述(Part 1)
- <;2013 12 28>; AOI PCB设计
- <;2013 12 01>; 一篇很好的关于windows编程的入门指导(2013年末写的,比较前沿)