let43 Multiply String

2024-03-29 18:18

文章标签 string multiply let43

本文主要是介绍let43 Multiply String，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

主题思想： 大数乘法，这里写一种大数乘法的通用模板，整体思路是：利用数组，一个int型数组表示长度为4的子串，为什么是4呢？因为int 型 21亿，1亿=10^9，长度为4最大值9999，两个值相乘<10^8 ，结果仍可以用一个int表示。
大体思路如下，把字符串，按每四位截取，并转换成int 存储在数组里

运算时，对int数组进行运算，输出结果需要注意，去除前导0，对于中间值为0的情况，要输出4个0.

代码：

class Solution {public String multiply(String num1, String num2) {if(num1==null||num1.length()==0) return "";if(num2==null||num2.length()==0) return "";int n=30;int[] arr1=new int[n];int[] arr2=new int [n];int [] sum=new int[2*n];for(int i=0;i<n;i++){arr1[i]=0;arr2[i]=0;}for(int i=0;i<2*n;i++)sum[i]=0;str2array(num1,arr1);str2array(num2,arr2);int carry=0;int tmp=0;for(int i=0;i<n;i++){carry=0;tmp=0;for(int j=0;j<n;j++){tmp=arr1[i]*arr2[j]+carry;sum[i+j]+=tmp;carry=sum[i+j]/10000;sum[i+j]=sum[i+j]%10000;}}String ans="";int start=2*n-1;for(int i=2*n-1;i>=0;i--){if(sum[i]!=0) {start=i;break;}}if(start==2*n-1) return "0";for(int j=start;j>=0;j--) {ans=ans+int2str(sum[j]);}start=0;for(int i=0;i<ans.length();i++){if(ans.charAt(i)!='0'){start=i;break;}}return ans.substring(start);}public void str2array(String num,int[] array){int len=(num.length()+3)/4;int tmp=0;for(int i=0;i<len;i++){tmp=num.length()-i*4;array[i]=str2int(num.substring(Math.max(tmp-4,0),tmp));}return ;}public int str2int(String str){int sum=0;for(int i=0;i<str.length();i++){sum=sum*10+(int)(str.charAt(i)-'0');}return sum;}public String int2str(int num){String s="";while(num!=0){s=(num%10)+s;num/=10;}int rawLen=s.length();for(int i=0;i<4-rawLen;i++){s="0"+s;}return s;}
}