首页 > 代码库 > 【leetcode刷题笔记】Multiply Strings
【leetcode刷题笔记】Multiply Strings
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。
代码如下：
1 public class Solution { 2 public String multiply(String num1, String num2) { 3 if(num1 == null || num2 == null) 4 return null; 5 int len1 = num1.length(); 6 int len2 = num2.length(); 7 int len3 = len1 + len2; 8 int[] numbers = new int[len3]; 9 10 int i,j;11 12 for(i = len1-1;i >= 0;i--){13 for(j=len2-1;j >= 0;j--){14 numbers[i+j+1] += (num1.charAt(i)-‘0‘) * (num2.charAt(j)-‘0‘);15 }16 }17 18 int carries = 0;19 for(i = len3-1;i >=0;i--){20 numbers[i] += carries;21 carries = numbers[i]/10;22 numbers[i] %= 10; 23 }24 25 26 StringBuffer sBuffer = new StringBuffer();27 sBuffer.append(numbers[0]==0?"":numbers[0]);28 i = 1;29 if(sBuffer.length() == 0){30 while(i < len3 && numbers[i]== 0)31 i++;32 }33 for(;i <len3;i++)34 sBuffer.append(numbers[i]);35 if(sBuffer.length() == 0)36 sBuffer.append(0);37 return sBuffer.toString();38 }39 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。