力扣(LeetCode)43

itvincent 發(fā)布于2019-08-16 15:57 / 1270人閱讀

摘要：示例輸入輸出示例輸入輸出說明和的長度小于。和均不以零開頭，除非是數(shù)字本身。舉例說明這兩個數(shù)的乘積的長度一定不會超過，分別是字符串的長度。第一輪第二輪至此該數(shù)組變?yōu)槿缓笤購奈膊刻幚磉M位。

題目地址：
https://leetcode-cn.com/probl...
題目描述：
給定兩個以字符串形式表示的非負整數(shù) num1 和 num2，返回 num1 和 num2 的乘積，它們的乘積也表示為字符串形式。

示例 1:

輸入: num1 = "2", num2 = "3"
輸出: "6"
示例 2:

輸入: num1 = "123", num2 = "456"
輸出: "56088"
說明：

num1 和 num2 的長度小于110。
num1 和 num2 只包含數(shù)字 0-9。
num1 和 num2 均不以零開頭，除非是數(shù)字 0 本身。
不能使用任何標準庫的大數(shù)類型（比如 BigInteger）或直接將輸入轉(zhuǎn)換為整數(shù)來處理。

解答：
如何使用計算機模仿大數(shù)想乘？
我們用手計算的時候，會邊乘邊計算進位，并且把進位加在前一位。
但是如果這里也這樣處理，那么會無比麻煩，實際上我們可以把每一位的乘積加上，然后
最后再統(tǒng)一處理。
舉例說明：
124 * 32
這兩個數(shù)的乘積的長度一定不會超過m+n（m，n分別是字符串的長度。）
我們開一個m+n長度的數(shù)組val[m+n]。
第一輪：2*4 = 8,val[m+n-1] += 8,val[m+n-1] = 8

   2*2 = 4,val[m+n-2] += 4,val[m+n-2] = 4
   2*1 = 2,val[m+n-3] += 2,val[m+n-3] = 2

第二輪：3*4 = 12,val[m+n-2] += 12,val[m+n-2] = 16

   3*2 = 6,val[m+n-3] += 6,val[m+n-3] = 8 
   3*1 = 3,val[m+n-4] += 3,val[m+n-4] = 3

至此,該數(shù)組變?yōu)?br>val[0,3,8,16,8]

然后再從尾部處理進位。
比如最后一位8是沒有進位的，往前處理，到了16，16 >= 10。
把該位變成16%10 = 6,并且獲得進位16/10 = 1,再繼續(xù)向前處理
8要加上進位變成9，然后再往前處理3不動。
最后數(shù)組變成val[0,3,9,6,8]
到此，絕大部分工作已經(jīng)完成，只需要從左掃描數(shù)組找到第一個不為0的數(shù)，然后把后面的加入字符串即可。

java ac代碼：

class Solution {
    
    public String multiply(String num1, String num2) {
        int[] val = new int[num1.length() + num2.length()];
        
        for(int i = num1.length()-1,round = 0;i >= 0;i--,round++){
            int k = val.length-1-round;
            for(int j = num2.length()-1;j >= 0;j--)
            {
                int temp = (num1.charAt(i)-"0")*(num2.charAt(j)-"0");
                val[k--] += temp;                
            }
        }
        int plus = 0;
        for(int i = val.length-1;i >= 0;i--)
        {
            int sum = val[i] + plus;
            val[i] = sum%10;
            plus = sum/10;
        }
        int loc = 0;
        String ans = "";
        while(loc < val.length && val[loc] == 0)loc++;
        if(loc == val.length)ans = "0";
        else
        for(int i = loc;i < val.length;i++)
            ans += val[i];
        return ans;
        
    }
}

更為詳細的講解可以參考這篇文章https://blog.csdn.net/afei__/...