leetcode 43 Multiply Strings

cloud 發(fā)布于2019-08-19 10:42 / 2963人閱讀

摘要：題目詳情題目要求輸入兩個以字符串形式表示的正整數(shù)，要求我們求出它們的乘積，同樣也是字符串形式表示。要求不能直接將字符串轉(zhuǎn)換為整數(shù)進行乘法運算。想法這道題的思路就是將我們平時手算多位數(shù)乘法的計算方法，轉(zhuǎn)換成程序語言。

題目詳情

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.
Note:
-The length of both num1 and num2 is < 110.
-Both num1 and num2 contains only digits 0-9.
-Both num1 and num2 does not contain any leading zero.
-You must not use any built-in BigInteger library or convert the inputs to integer directly.題目要求輸入兩個以字符串形式表示的正整數(shù)，要求我們求出它們的乘積，同樣也是字符串形式表示。要求不能直接將字符串轉(zhuǎn)換為整數(shù)進行乘法運算。

想法

這道題的思路就是將我們平時手算多位數(shù)乘法的計算方法，轉(zhuǎn)換成程序語言。

對于兩個長度分別為m,n的字符串，乘法操作獲得的字符串res長度為m+n(第一位可以是0)

首先我們看一下下面這張圖

這個例子里我們的操作順序是，用5分別乘以1，2，3；隨后再用4分別乘以1，2，3.每次對位的乘法操作我們默認(rèn)他會獲得一個兩位數(shù)(第一位可以是0)

如果進行乘法操作的兩位在各自字符串中的位置為i和j，那么生成的兩位數(shù)在結(jié)果字符串res中對應(yīng)的位置應(yīng)當(dāng)是i+j和i+j+1

將乘法結(jié)果和對應(yīng)位置上的已有數(shù)相加，再將結(jié)果放到對應(yīng)位置。

解法

    public String multiply(String num1, String num2) {
        int m = num1.length();
        int n = num2.length();
        int[] pos = new int[m+n];
        
        //計算
        for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                int mul = (num1.charAt(i)-"0")*(num2.charAt(j)-"0");
                int p1 = i + j;
                int p2 = i + j + 1;
                
                int sum = mul + pos[p2];
                pos[p1] += sum / 10;
                pos[p2] = sum % 10;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for(int p : pos) if(!(sb.length() == 0 && p == 0)) sb.append(p);
        return sb.length() == 0 ? "0" : sb.toString();
    }