字符串之大数乘法
描述
以字符串的形式读入两个数字,编写一个函数计算它们的乘积,以字符串形式返回。
数据范围: 读入的数字大小满足 0 \le n \le 10^{1000}0≤n≤10
1000
思路一:建议使用
就是平常我们做乘法的步骤,先相乘,再相加, 最后统一处理进位。
优化之后就是直接算乘法,把 num1 的每一位数字 和 num2 的每一位数字相乘, 相乘的结果放到对应的位置上,最后我们再处理相乘之后的结果即可。
如果 num1 的长度为 N , num2 的长度为 M, 则 num1 * num2 的结果最长长度为 N + M,所以开辟一个长度为 N + M 的整型数组来操作相乘的结果。
最后处理进位:
package test;
public class BigCheng4 {
public static void main(String[] args) {
BigCheng4 bigCheng4 = new BigCheng4();
String solve = bigCheng4.solve("12", "999");//96726
System.out.println(solve);
}
public String solve(String s, String t) {
//1.判断空
if(s.length()==0 || t.length()==0)
return "0";
if("0".equals(s)||"0".equals(t))
return "0";
//用于存最后结果的整型数组
int res[]=new int[s.length()+t.length()];
//2.处理乘法和累加计算
for (int i = s.length()-1; i >=0 ; i--) {
for (int j = t.length()-1; j >=0 ; j--) {
res[i+j+1] = res[i+j+1]+
(s.charAt(i)-'0')*(t.charAt(j)-'0');
}
}
/**
* 测试数组累加结果
* for (int re : res) {
* System.out.print(re+ " ");
* }
*/
//3.处理最后的进位
int carry=0;
StringBuffer buffer = new StringBuffer();
for (int i = res.length-1; i >=0 ; i--) {
//先加数
int curRes = res[i]+carry;
buffer.append(curRes % 10);//将个位数串起来
carry=curRes/10;
}
String s1 = buffer.reverse().toString();
//System.out.println(s1);,
//去掉多于的前面的0
if(s1.charAt(0)=='0'){
return s1.substring(1);
}else{
return s1;
}
}
}
思路二:数学模拟法
代码演示:
思路相当于2轮循环:第一轮相当于123x5=615
第二轮相当于123x40 = 4920
然后相加两轮结果即可;
package test;
public class BigCheng2 {
public static void main(String[] args) {
BigCheng2 bigCheng2 = new BigCheng2();
String solve = bigCheng2.solve("123", "45");
System.out.println(solve);
}
public static String solve (String s, String t) {
//判空
if(s.length()==0 || t.length() == 0)
return "0";
if("0".equals(s) || "0".equals(t))
return "0";
//字符串进行反转操作
StringBuffer reverse_s = new StringBuffer(s).reverse();
StringBuffer reverse_t = new StringBuffer(t).reverse();
//找出段字符串进行外层循环
StringBuffer shortStr =
reverse_s.length()<reverse_t.length()?reverse_s:reverse_t;
StringBuffer longStr =
reverse_s.length()>=reverse_t.length()?reverse_s:reverse_t;
//开始循环计算结果
int res[] = new int[s.length()+t.length()];//存放结果
int up = 0;//开始的进位
for (int i = 0; i < shortStr.length(); i++) {
int k = i;//k每一次循环进行累加,相当于下标计数器,
up = 0;//每一轮进位重置为0
for (int j = 0; j < longStr.length(); j++) {
//临时的一个数字相乘的结果+进位+原先数组的结果
int curRes =
(shortStr.charAt(i)-'0')*(longStr.charAt(j)-'0')+up+res[k];
//求进位和当前位置数res[k]
res[k] = curRes % 10;
up = curRes /10;
k++;//下标增加
}
//一轮计算完毕后,再向前一位计算进位,防止有进位的
res[k] = res[k]+ up;
}
//统计结果,并反转
StringBuffer buffer = new StringBuffer();
for (int i = 0; i < res.length; i++) {
buffer.append(res[i]);
}
String s1 = buffer.reverse().toString();
if(s1.charAt(0)=='0'){
return s1.substring(1);
}else{
return s1;
}
}
}
百香熊猫果: 掉了一步,修改完/etc/profile 记得source /etc/profile是配置文件生效
拯救micheal计划: 同样是硅谷大学毕业,你为何如此优秀
Gao__xi: 第一步:开启save配置,即打开save x x,也就是关闭RDB模式??不是很懂,开启save配置不是开启RDB吗?
可爱元气: 如果source完成还是报错呢
呆瓜-hao: 我丢,这么长