拼多多校招编程题--大整数相乘(Java实现)

题目描述

有两个用字符串表示的非常大的大整数,算出他们的乘积，也是用字符串表示。不能用系统自带的大整数类型。

思路：

（1）参考乘法计算，随机取一个乘数1，并从后向前遍历i

（2）用另外一个乘数2，并从后向前遍历j，用i乘j，遍历到j的十位时，记得在末位加一个0，百位加2个，千位加3个，依次下去。

（3）每遍历一个字符，得到一个结果并放入数组

（4）取这个数组最后一个字符串就是最长的字符串，以其长度为基准，向数组中其他元素前面添加一定数量的‘0’，保证所有元素的长度相等

（5）然后，遍历该数组，从后向前遍历字符串，每个纵列相加，结果对10分别取整和取余数，整进1位即在下次计算纵列相加时加上这个数，余则赋值当前索引位置字符

（6）如果遍历完成后，进位仍然大于0，就在字符串前面加上这个进位字符，此时针对（乘数1）乘（乘数2）个位已经算完成

（7）后面就是遍历所有乘数1了，方法和前面一样

（8）注意，到最后，得到（乘数2）乘（乘数1）乘所有字符的数组，该数组长度是乘数1字符的长度，在初始化时需要注意，当然也可以使用ArrayList。

以上思路，是我个人的，仅供参考，代码如下：

import java.util.Scanner;

public class Main {
//        前面少的补'0'
    static String[] addZero(String[] s) {
        int lastCharLength = s[s.length - 1].length();
        for (int i = 0; i < s.length - 1; i++) {
            StringBuilder temp1 = new StringBuilder();
            for (int j = 0; j < lastCharLength - s[i].length(); j++) {
                temp1.append('0');//位数大的后面补0
            }
            s[i] = temp1.toString() + s[i];
        }
        return s;
    }

    static String[] cal2(String s1, char c1, int eLength) {
        int index = s1.length() - 1, e = 0;
        char[] c = s1.toCharArray();
        String[] s = new String[c.length];
        while (index > -1) {
            int temp = Integer.parseInt(String.valueOf(c1)) * Integer.parseInt(String.valueOf(c[index]));
            StringBuilder temp1 = new StringBuilder(String.valueOf(temp));
            for (int i = 0; i < e + eLength; i++) {
                temp1.append('0');//位数大的后面补0
            }
            s[e] = temp1.toString();
            index -= 1;
            e += 1;
        }
        //        前面少的补'0'
        return addZero(s);
    }

    static String add(String[] s1) {
        int index = s1[0].length() - 1;
        char[] chars = new char[s1[0].length()];
        int pretemp = 0;
        while (index > -1) {
            int persum = 0;
            for (int i = 0; i < s1.length; i++) {
                persum += Integer.parseInt(String.valueOf(s1[i].charAt(index)));
            }
            persum += pretemp;
            pretemp = persum / 10;
            chars[index] = String.valueOf(persum % 10).charAt(0);
            index -= 1;
        }
        if (pretemp > 0) return String.valueOf(pretemp) + String.valueOf(chars);
        else return String.valueOf(chars);
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String line = input.nextLine();
        String[] lines = line.split(" ");
        String partLine1 = lines[0], partLine2 = lines[1];
        int eLength = 0;
        String[] strings = new String[partLine2.length()];
        for (int i = partLine2.length() - 1; i >= 0; i--) {
            String[] s = cal2(partLine1, partLine2.charAt(i), eLength);
            strings[eLength] = add(s);
            eLength += 1;
        }
        System.out.println(add(addZero(strings)));
    }
}

运行结果：