题解 | #大数乘法#

import java.math.BigInteger;
import java.util.*;

/**
 * NC10 大数乘法
 * @author d3y1
 */
public class Solution {
    private String result = "";

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串 第一个整数
     * @param t string字符串 第二个整数
     * @return string字符串
     */
    public String solve (String s, String t) {
        // return solution1(s, t);
        return solution2(s, t);
        // return solution3(s, t);
    }

    /**
     * 模拟法
     * @param s
     * @param t
     */
    private String solution1(String s, String t){
        if(s.length() < t.length()){
            String tmp = s;
            s = t;
            t = tmp;
        }
        int sLen = s.length();
        int tLen = t.length();

        String product;
        int tDigit;
        for(int i = 1; i <= tLen; i++){
            tDigit = t.charAt(tLen-i)-'0';
            product = multiplier(s, tDigit, i-1);
            result = adder(result, product);
        }

        return result;
    }

    /**
     * 乘法器
     * @param s
     * @param tDigit
     * @param offset
     * @return
     */
    private String multiplier(String s, int tDigit, int offset){
        if(tDigit == 0){
            return "0";
        }

        StringBuilder multi = new StringBuilder();
        int sLen = s.length();
        int sDigit,digit;
        int product;
        int carry = 0;
        for(int i = 1; i <= sLen; i++){
            sDigit = s.charAt(sLen-i)-'0';
            product = sDigit * tDigit + carry;
            digit = product % 10;
            carry = product / 10;
            multi.insert(0, digit);
        }
        if(carry > 0){
            multi.insert(0, carry);
        }
        while(offset-- > 0){
            multi.append(0);
        }

        return multi.toString();
    }

    /**
     * 加法器
     * @param s
     * @param t
     * @return
     */
    private String adder(String s, String t){
        if(s.equals("")){
            return t;
        }
        if(t.equals("")){
            return s;
        }

        int sLen = s.length();
        int tLen = t.length();
        int len = Math.max(sLen, tLen);

        int carry = 0;
        int sum,sDigit,tDigit,digit;
        StringBuilder result = new StringBuilder();
        for(int i = 1; i <= len; i++){
            sDigit = (sLen-i >= 0) ? s.charAt(sLen-i)-'0' : 0;
            tDigit = (tLen-i >= 0) ? t.charAt(tLen-i)-'0' : 0;
            sum = sDigit + tDigit + carry;
            carry = sum / 10;
            digit = sum % 10;
            result.insert(0, digit);
        }
        if(carry > 0){
            result.insert(0, carry);
        }

        return result.toString();
    }

    /**
     * 交叉相乘法
     * @param s
     * @param t
     * @return
     */
    private String solution2(String s, String t){
        int sLen = s.length();
        int tLen = t.length();

        int[] sDigits = new int[sLen];
        int[] tDigits = new int[tLen];
        for(int i = 0; i < sLen; i++){
            sDigits[i] = s.charAt(i)-'0';
        }
        for(int i = 0; i < tLen; i++){
            tDigits[i] = t.charAt(i)-'0';
        }

        // 交叉相乘
        int[] result = new int[sLen+tLen];
        for(int i = 0; i < sLen; i++){
            for(int j = 0; j < tLen; j++){
                result[i+j+1] += sDigits[i] * tDigits[j];
            }
        }

        int carry = 0;
        for(int i = sLen+tLen-1; i >= 0; i--){
            result[i] += carry;
            carry = result[i] / 10;
            result[i] %= 10;
        }

        boolean foundBeginning = false;
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < sLen+tLen; i++){
            if(!foundBeginning){
                if(result[i] > 0){
                    sb.append(result[i]);
                    foundBeginning = true;
                }
            }else{
                sb.append(result[i]);
            }
        }

        return sb.length()==0 ? "0" : sb.toString();
    }

    /**
     * 库函数: BigInteger
     * @param s
     * @param t
     * @return
     */
    private String solution3(String s, String t){
        BigInteger bigIntegerS = new BigInteger(s);
        BigInteger bigIntegerT = new BigInteger(t);

        return bigIntegerS.multiply(bigIntegerT).toString();
    }
}