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

- 日理万妓 2022-03-16 10:36 249阅读 0赞

## 题目描述 ##

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70][]

思路：

（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)));
        }
    }

运行结果：

![20190227161916445.png][]

顺便吐槽一下，这个在线编辑器太难用了，还是本地的好用，要是考试就gg了。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70]: /images/20220316/7057f2ccdefc4ae7b68da7b4e511e413.png
[20190227161916445.png]: /images/20220316/9bad5d67cf3e4f298d319d1f081c5fc3.png