[Leetcode] Multiply String and Big Interger 大數(shù)乘法加法

keithxiaoy 發(fā)布于2019-08-14 12:47 / 3350人閱讀

摘要：因?yàn)楸怀藬?shù)每一位數(shù)字和乘數(shù)相乘的結(jié)果是依次錯(cuò)開(kāi)的，所以就沒(méi)問(wèn)題。判斷兩個(gè)數(shù)的大小的方法，是先判斷其長(zhǎng)度，如果長(zhǎng)度不一樣，則較長(zhǎng)的較大，如果長(zhǎng)度一樣，則需要比較每一位。

Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.

模擬乘法 復(fù)雜度

時(shí)間 O(NM) 空間 O(N+M)

思路

這題的技巧在于復(fù)用同一個(gè)結(jié)果數(shù)組存放上次的計(jì)算結(jié)果。因?yàn)楸怀藬?shù)每一位數(shù)字和乘數(shù)相乘的結(jié)果是依次錯(cuò)開(kāi)的，所以就沒(méi)問(wèn)題。

注意

轉(zhuǎn)換回String前要先把前面的0去掉，但第一位的0不去掉

代碼

public class Solution {
    public String multiply(String num1, String num2) {
        if(num1 == null || num2 == null) return null;
        int len1 = num1.length(), len2 = num2.length();
        // 結(jié)果的位數(shù)最多可能是兩個(gè)乘數(shù)位數(shù)之和
        int len3 = len1 + len2;
        int[] res = new int[len3];
        int carry = 0, i = 0, j = 0;
        for(i = len1 - 1; i >= 0; i--){
            // 先置carry位為0
            carry = 0;
            for(j = len2 - 1; j >= 0; j--){
                // 每一位的乘積，等于之前這一位的結(jié)果，加上carry，再加上這一位和乘數(shù)的乘積
                int product = carry + res[i + j + 1] + (num1.charAt(i) - "0")*(num2.charAt(j) - "0");
                res[i + j + 1] = product % 10;
                carry = product / 10;
            }
            // 把最后的carry位加上
            res[i + j + 1] = carry;
        }
        StringBuilder resstr = new StringBuilder();
        i = 0;
        // 跳過(guò)前面無(wú)用的0
        while(i < len3 - 1 && res[i] == 0){
            i++;
        }
        for(; i < len3; i++){
            resstr.append(res[i]);
        }
        return resstr.toString();
    }
}

Add Two Strings 模擬加法 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

從后向前模擬加法

代碼

private String addString(String num1, String num2){
    int i = num1.length() - 1, j = num2.length() - 1;
    int k = Math.max(i, j);
    int[] num3 = new int[k + 1];
    int sum = 0, carry = 0;
    while(i >= 0 || j >= 0){
        // 加數(shù)的位
        int d1 = i >= 0 ? (num1.charAt(i) - "0") : 0; 
        // 被加數(shù)的位
        int d2 = j >= 0 ? (num2.charAt(j) - "0") : 0;
        sum = d1 + d2 + carry;
        num3[k] = sum % 10;
        carry = sum / 10;
        k--;
        i--;
        j--;
    }
    StringBuilder sb = new StringBuilder();
    // 如果最后還有進(jìn)位要加上
    if(carry != 0) sb.append(carry);
    for(int digit : num3){
        sb.append(digit);
    }
    return sb.toString();
}

有符號(hào)加法 思路

有符號(hào)的話，就要根據(jù)符合判斷具體的操作

如果都是負(fù)數(shù)，則結(jié)果是兩個(gè)絕對(duì)值相加再取負(fù)

如果一個(gè)是負(fù)數(shù)一個(gè)正數(shù)，則結(jié)果是（正數(shù)）減去（負(fù)數(shù)的絕對(duì)值），這里要用到減法

如果都是正數(shù)則直接相加

代碼

private static String addSignedString(String num1, String num2){
    int sign1 = 1, sign2 = 1;
    if(num1.charAt(0) == "-"){
        sign1 = -1;
        num1 = num1.substring(1);
    }
    if(num2.charAt(0) == "-"){
        sign2 = -1;
        num2 = num2.substring(1);
    }
    if(sign1 == sign2){
        String res = addString(num1, num2);
        return sign1 == -1 ? "-" + res : res;
    } else {
        if(sign1 == 1){
            return subString(num1, num2);
        } else {
            return subString(num2, num1);
        }
    }
}

Substract Two Strings 模擬減法 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

從后向前模擬減法，計(jì)算每一位的值時(shí)，用減數(shù)的位減去被減數(shù)，再加上10，再減去借位，結(jié)果模上10就行了。借位則是看之前的結(jié)果是否小于10，如果小于10說(shuō)明借位了。不過(guò)要注意的是，我們要用較大的數(shù)減去較小的數(shù)，如果減數(shù)反而較大，我們要用減數(shù)減去被減數(shù)，然后結(jié)果加上負(fù)號(hào)。判斷兩個(gè)數(shù)的大小的方法，是先判斷其長(zhǎng)度，如果長(zhǎng)度不一樣，則較長(zhǎng)的較大，如果長(zhǎng)度一樣，則需要比較每一位。

代碼

private static String subString(String num1, String num2){
    int len1 = num1.length(), len2 = num2.length();
    // 根據(jù)兩數(shù)的大小關(guān)系，決定是直接相減，還是反過(guò)來(lái)相減取負(fù)
    if(len1 > len2){
        return coreSub(num1, num2);
    } else if (len1 < len2){
        return "-"+coreSub(num2, num1);
    } else {
        int compare = num1.compareTo(num2);
        if(compare > 0){
            return coreSub(num1, num2);
        } else if(compare < 0){
            return "-"+coreSub(num2, num1);
        } else {
            return "0";
        }
    }
}

private static String coreSub(String num1, String num2){
    int i = num1.length() - 1, j = num2.length() - 1;
    int[] num3 = new int[i + 1];
    int diff = 0, borrow = 0;
    while(i >= 0){
        int d1 = num1.charAt(i) - "0";
        int d2 = j >= 0? num2.charAt(j) - "0": 0;
        // 計(jì)算差值時(shí)要先加上10
        diff = d1 + 10 - borrow - d2;
        num3[i] = diff % 10;
        borrow = diff < 10 ? 1 : 0;
        i--;
        j--;
    }
    i = 0;
    while(num3[i] == 0){
        i++;
    }
    StringBuilder sb = new StringBuilder();
    while(i < num3.length){
        sb.append(num3[i]);
        i++;
    }
    return sb.toString();
}

有符號(hào)減法 代碼

private static String subSignedString(String num1, String num2){
    int sign1 = 1, sign2 = 1;
    if(num1.charAt(0) == "-"){
        sign1 = -1;
        num1 = num1.substring(1);
    }
    if(num2.charAt(0) == "-"){
        sign2 = -1;
        num2 = num2.substring(1);
    }
    if(sign1 == sign2){
        // 都是正數(shù)則直接相減
        if(sign1 == 1){
            return subString(num1, num2);
        // 都是負(fù)數(shù)則后面減去前面
        } else {
            return subString(num2, num1);
        }
    } else {
        // 前正后負(fù)則相加
        if(sign1 == 1){
            return addString(num1, num2);
        // 前負(fù)后正則相加后取負(fù)
        } else {
            return "-"+addString(num1, num2);
        }
    }
}