本文主要是介绍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;}
}
这篇关于let43 Multiply String的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!