拼多多校招程式設計題--大整數相乘(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)));
    }
}
           

運作結果：

順便吐槽一下，這個線上編輯器太難用了，還是本地的好用，要是考試就gg了。