字串相乘-java解法

給定兩個以字串形式表示的非負整數 num1 和 num2，返回 num1 和 num2 的乘積，它們的乘積也表示爲字串形式。

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

範例 1:

輸入: num1 = 「2」, num2 = 「3」
輸出: 「6」

範例 2:

輸入: num1 = 「123」, num2 = 「456」
輸出: 「56088」

說明：

num1 和 num2 的長度小於110。
num1 和 num2 只包含數位 0-9。
num1 和 num2 均不以零開頭，除非是數位0 本身。
不能使用任何標準庫的大數型別（比如 BigInteger）或直接將輸入轉換爲整數來處理。

解法：

豎式相乘法：

豎式運算思想，以 num1 爲 123，num2 爲 456 爲例分析

遍歷 num2 每一位與 num1 進行相乘，將每一步的結果進行累加。

注意：

num2 除了第一位的其他位與 num1 運算的結果需要 補0
計算字串數位累加其實就是 415. 字串相加

程式碼：

class Solution {
    public String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0")){
                return "0";
        }String res = "0";
        //如果兩個數中有一個爲0，則結果爲0
        for(int i = num2.length()-1;i>=0;i--){
        	//從最低位到最高位，取nums2的每一位與nums1相乘
            StringBuilder temp = new StringBuilder();
            //新建sb儲存每次的結果
            int carry = 0;
            //進位識別符號
            for(int j = 0; j<num2.length()-i-1;j++){
                temp.append("0");
                //加0操作，因爲是從最低位計算，最後字串需要reverse（），所以0加在字串最前面
            }
            int curN2 = num2.charAt(i)-'0';
            //從最低位到最高位取nums2的每一位
            for(int j = num1.length()-1;j>=0 || carry != 0;j--){
            	//n2與n1的每一位相乘，依然是從最低位到最高位
                int curN1  = j < 0 ? 0:num1.charAt(j)-'0';
                int cur = (curN1*curN2+carry) %10;
                //當前位置乘積後的數
                carry = (curN1*curN2+carry) /10;
                //當前位置進位識別符號
                temp.append(cur);
                //存入當前位置
            }
            res = addString(res,temp.reverse().toString());
            //將每次n2的某一位與n1的乘積結果與之前的記錄相加

        }return res;
    }private String addString(String num1,String  num2){
        StringBuilder temp = new StringBuilder();
        int carry = 0;
        for(int i = num1.length()-1, j = num2.length()-1;i>=0||j>=0||carry!=0;i--,j--){
        	//同上
            int n1 = i<0? 0:num1.charAt(i)-'0';
            int n2 = j<0? 0:num2.charAt(j)-'0';
            int sum = (carry+n1+n2)%10;
            carry = (carry+n1+n2)/10;
            temp.append(sum);

        }return temp.reverse().toString();
        //因爲是從最低位到最高位存入的，所以最後需要reverse（）
    }
}