就是两个数相乘,输出结果,只不过数字很大很大,都是用 String 存储的。也就是传说中的大数相乘。
解法一
我们就模仿我们在纸上做乘法的过程写出一个算法。
个位乘个位,得出一个数,然后个位乘十位,全部乘完以后,就再用十位乘以各个位。然后百位乘以各个位,最后将每次得出的数相加。十位的结果要补 1 个 0 ,百位的结果要补两个 0 。相加的话我们可以直接用之前的大数相加。直接看代码吧。
publicStringmultiply(Stringnum1, Stringnum2) { if (num1.equals("0") ||num2.equals("0")) { return"0"; } Stringans="0"; intindex=0; //记录当前是哪一位,便于后边补 0 for (inti=num2.length() -1; i>=0; i--) { intcarry=0; //保存进位Stringans_part=""; //直接用字符串保存每位乘出来的数intm=num2.charAt(i) -'0'; //乘上每一位for (intj=num1.length() -1; j>=0; j--) { intn=num1.charAt(j) -'0'; intmul=m*n+carry; ans_part=mul%10+""+ans_part; carry=mul/10; } if (carry>0) { ans_part=carry+""+ans_part; } //补 0 for (intk=0; k<index; k++) { ans_part=ans_part+"0"; } index++; //和之前的结果相加ans=sumString(ans, ans_part); } returnans; } //大数相加privateStringsumString(Stringnum1, Stringnum2) { intcarry=0; intnum1_index=num1.length() -1; intnum2_index=num2.length() -1; Stringans=""; while (num1_index>=0||num2_index>=0) { intn1=num1_index>=0?num1.charAt(num1_index) -'0' : 0; intn2=num2_index>=0?num2.charAt(num2_index) -'0' : 0; intsum=n1+n2+carry; carry=sum/10; ans=sum%10+""+ans; num1_index--; num2_index--; } if (carry>0) { ans=carry+""+ans; } returnans; }
时间复杂度:O(m * n)。m,n 是两个字符串的长度。
空间复杂度:O(1)。
总
如果按普通的思路写,这道题也不难。新的竖式的计算,让人眼前一亮,代码优雅了很多。