大数相乘-LeetCode43-字符串相乘
题目
给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
说明:
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头,除非是数字 0 本身。
不能使用任何标准库的大数类型(比如 BigInteger)或直接将输入转换为整数来处理。
思路1
模拟乘法过程,记录每个个位值和进位值。按列求和。
代码1
class Solution {
public String multiply(String num1, String num2) {
//String num1 转化为 int[]
int[] num1_array=new int[num1.length()];
for(int i=0;i<num1.length();i++){
num1_array[i]=Integer.parseInt(num1.substring(num1.length()-1-i,num1.length()-1-i+1));
}
//String num2 转化为 int[]
int[] num2_array=new int[num2.length()];
for(int i=0;i<num2.length();i++){
num2_array[i]=Integer.parseInt(num2.substring(num2.length()-1-i,num2.length()-1-i+1));
}
// 乘积结果 int[]
int[] res_array=new int[num1.length()+num2.length()];
// 个位值 int[][]
int[][] weivalue=new int[num2.length()][num1.length()+num2.length()];
// 进位值 int[][]
int[][] jinwei=new int[num2.length()][num1.length()+num2.length()];
// 求和进位 int[]
int[] qiuhejinwei=new int[num1.length()+num2.length()+1];
// 填充 个位值int[][] 和 进位值int[][]
for(int i=0;i<num2_array.length;i++){
for(int j=0;j<num1_array.length;j++){
int mul=num2_array[i]*num1_array[j];
int mulshiwei=(mul-mul%10)/10;
int mulgewei=mul%10;
jinwei[i][i+j+1]=mulshiwei;
weivalue[i][i+j]=mulgewei;
}
}
//列求和
for(int i=0;i<res_array.length;i++){
res_array[i]=0;
for(int j=0;j<weivalue.length;j++){
res_array[i]+=weivalue[j][i];
}
for(int j=0;j<jinwei.length;j++){
res_array[i]+=jinwei[j][i];
}
res_array[i]+=qiuhejinwei[i];
int res_array_gewei=res_array[i]%10;
int res_array_shiwei=(res_array[i]-res_array[i]%10)/10;
qiuhejinwei[i+1]=res_array_shiwei;
res_array[i]=res_array_gewei;
}
String res="";
// 乘积结果int[]倒叙
for(int i=res_array.length-1;i>=0;i--){
res+=res_array[i]+"";
}
// 去掉前面的0
for(int i=0;i<res.length();i++){
if(res.charAt(i)=='0'){
res=res.substring(1);
i--;
}else{
break;
}
}
if(res.length()==0){
return 0+"";
}
return res;
}
}
思路2
不用记录每个个位值和进位值,用到时再算。按列求和。
class Solution {
public String multiply(String num1, String num2) {
int[] num1_array=new int[num1.length()];
for(int i=0;i<num1.length();i++){
num1_array[i]=Integer.parseInt(num1.substring(num1.length()-1-i,num1.length()-1-i+1));
}
int[] num2_array=new int[num2.length()];
for(int i=0;i<num2.length();i++){
num2_array[i]=Integer.parseInt(num2.substring(num2.length()-1-i,num2.length()-1-i+1));
}
int[] res_array=new int[num1.length()+num2.length()+3];
int qiuhejinwei=0;
for(int k=0;k<res_array.length;k++){
res_array[k]=0;
// 取个位
for(int i=0;i<num2_array.length;i++){
int j=k-i;
if(j>=num1_array.length || j<0){
continue;
}
res_array[k]+=(num1_array[j]*num2_array[i])%10;
}
// 取进位
for(int i=0;i<num2_array.length;i++){
int j=k-i-1;
if(j>=num1_array.length || j<0){
continue;
}
res_array[k]+=(num1_array[j]*num2_array[i]-(num1_array[j]*num2_array[i])%10)/10;
}
// 加上求和进位
res_array[k]+=qiuhejinwei;
int res_array_gewei=res_array[k]%10;
int res_array_shiwei=(res_array[k]-res_array[k]%10)/10;
qiuhejinwei=res_array_shiwei;
res_array[k]=res_array_gewei;
}
String res="";
for(int i=res_array.length-1;i>=0;i--){
res+=res_array[i]+"";
}
for(int i=0;i<res.length();i++){
if(res.charAt(i)=='0'){
res=res.substring(1);
i--;
}else{
break;
}
}
if(res.length()==0){
return 0+"";
}
return res;
}
}