leetcode 43. Multiply Strings 9大数相差（java实现）

原题：

Given two non-negative integers?num1?and?num2?represented as strings,return the product of?num2.

Note:

1. The length of both?num2?is < 110.
2. Both?num2?contains only digits?0-9.
3. Both?num2?does not contain any leading zero.
4. You?must not use any built-in BigInteger library?or?convert the inputs to integer?directly.

就是大数相乘，以两个字符串的形式将大数读入，按照笔算的规则来计算，从各位开始逐位相乘，设置一个数组来不断累加乘积结果，最后将结果倒过来。

代码如下：

public class Solution {
    public String multiply(String num1,String num2) {
        if(num1=="" || num2=="") return "";
        if(num1.equals("0") || num2.equals("0")) return "0";
        int len1=num1.length();
        int len2=num2.length();
        int[] multi = new int[len1+len2];
        int cur = 0;
        int k = 0;
        for(int i=len2-1;i>=0;i--){
        	cur = len2-i-1;//用来保存当前乘数是第几位的，因为每乘一遍就相加，需要保存错位的位数
        	k=cur;
        	int b = num2.charAt(i)-'0';
        	for(int j=len1-1;j>=0;j--){
        		int a = num1.charAt(j)-'0';
        		int c = a*b;
        		multi[k] = multi[k]+c%10;//保存对应两位相乘得到的个位数
        		if(multi[k]>9){
        			int temp = multi[k];
        			multi[k]= temp%10;
        			multi[k+1] = multi[k+1]+temp/10;
        		}//因为数组每个值保存的数字不能大于10，所以需要这样的处理
        		multi[k+1] = multi[k+1]+c/10;
        		if(multi[k+1]>9){
        			int temp = multi[k+1];
        			multi[k+1]= temp%10;
        			multi[k+2] = multi[k+2]+temp/10;
        		}
        		k++;
        	}
        }
        StringBuilder a = new StringBuilder();
        String result ="";
        if(multi[k]!=0) a.append(multi[k]);
        for(int i =k-1;i>=0;i--){
        	a.append(multi[i]);
        }
        result = a.toString();
        return result;
    }
}

（编辑：晋中站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!