leetcode 43.字符串相乘

原题

43.字符串相乘
2020年8月13日 每日一题

题解

题目说，给定的数字位数最高可达109，这就已经远超出了int甚至long的范围限制，因此需要另寻他法。

方法一

/*
@v7fgg
执行用时：27 ms, 在所有 Java 提交中击败了16.95%的用户
内存消耗：40.5 MB, 在所有 Java 提交中击败了5.58%的用户
2020年8月13日 8:19
*/
class Solution {
    public String multiply(String num1, String num2) {
        if(num1.equals("0")||num2.equals("0")){
            return "0";
        }
        String ans="0";
        for(int i=0;i<num2.length();i++){
            String zhongjian=chengfa(num1,num2.charAt(num2.length()-1-i));
            ans=jiafa(ans,zhongjian,i);
        }
        return ans;
    }
    public String chengfa(String s,char c){
        //计算一个大数s和一个个位数c的乘积
        if(c=='0'){return "0";}
        StringBuilder res=new StringBuilder();
        int mul=c-'0';
        int carr=0;
        for(int i=s.length()-1;i>=0;i--){
            int smul=s.charAt(i)-'0';
            int prod=mul*smul;
            res.append((prod+carr)%10);
            carr=(prod+carr)/10;
        }
        if(carr>0){
            res.append(carr);
        }        
        return res.reverse().toString();
    }
    public String jiafa(String s1,String s2,int cuowei){
        //计算俩数相加（考虑错位）
        StringBuilder s=new StringBuilder(s2);
        for(int k=0;k<cuowei;k++){
            s.append(0);
        }
        s2=s.toString();
        String duan="";
        String chang="";
        if(s1.length()>s2.length()){
            chang=s1;
            duan=s2;
        }
        else{
            duan=s1;
            chang=s2;
        }
        int i=chang.length()-1;
        int j=duan.length()-1;
        int jinwei=0;
        StringBuilder ans=new StringBuilder();
        while(j>=0){
            int a=chang.charAt(i)-'0';
            int b=duan.charAt(j)-'0';
            int he=a+b+jinwei;
            ans.append(he%10);
            jinwei=he/10;
            i--;
            j--;
        }
        while(i>=0){
            int he=chang.charAt(i)-'0'+jinwei;
            ans.append(he%10);
            jinwei=he/10;
            i--;
        }
        if(jinwei==1){
            ans.append(jinwei);
        }        
        return ans.reverse().toString();
    }
}

方法二

/*
@v7fgg
执行用时：4 ms, 在所有 Java 提交中击败了91.02%的用户
内存消耗：39.8 MB, 在所有 Java 提交中击败了56.73%的用户
2020年8月13日 12:04
*/
class Solution {
    public String multiply(String num1, String num2) {
        if(num1.equals("0")||num2.equals("0")){return "0";}
        //类比，比如三位数*三位数最多6位（但是此时最高位可以另存在jinwei里面），最少5位
        int prod[]=new int[num1.length()+num2.length()-1];
        for(int i=0;i<num1.length()+num2.length()-1;i++){
            for(int j=Math.max(0,i+1-num1.length());j<=Math.min(i,num2.length()-1);j++){
                prod[i]+=(num1.charAt(i-j)-'0')*(num2.charAt(j)-'0');
            }
        }
        StringBuilder ans=new StringBuilder();
        int jinwei=0;
        for(int i=num1.length()+num2.length()-2;i>=0;i--){
            int sum=jinwei+prod[i];
            ans.append(sum%10);
            jinwei=sum/10;
        }
        if(jinwei>0){
            ans.append(jinwei);
        }
        return ans.reverse().toString();
    }
}

方法三

免俗不能落掉BigInteger这种方法。不过需要注意的是lc的oj里面默认没有导入java.math.BigInteger，因此需要自己手动导入。

/*
@v7fgg
执行用时：14 ms, 在所有 Java 提交中击败了33.62%的用户
内存消耗：40.1 MB, 在所有 Java 提交中击败了31.91%的用户
2020年8月13日 14:55
*/
import java.math.*;
class Solution {
    public String multiply(String num1, String num2) {
        return new BigInteger(num1).multiply(new BigInteger(num2)).toString();
    }
}