Multiply Strings(43 Medium)

大数乘法加法减法(From Here)

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.

模拟乘法

复杂度

时间 O(NM) 空间 O(N+M)

思路

这题的技巧在于复用同一个结果数组存放上次的计算结果。因为被乘数每一位数字和乘数相乘的结果是依次错开的，所以就没问题。

public String multiply(String num1, String num2) {
    if(num1 == null || num2 == null) return null;
    int len1 = num1.length(), len2 = num2.length();

    //结果的位数最多可能是两个乘数位数之和
    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--){
            //每一位的乘积，等于之前这一位的结果，加上carry，再加上这一位和乘数的乘积
            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;

    // 跳过前面无用的0
    while(i < len3 - 1 && res[i] == 0){
        i++;
    }

    for(; i < len3; i++){
        resstr.append(res[i]);
    }

    return resstr.toString();
}

模拟加法

复杂度

时间 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){
        // 加数的位
        int d1 = i >= 0 ? (num1.charAt(i) - '0') : 0;
        // 被加数的位
        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();

    // 如果最后还有进位要加上
    if(carry != 0) sb.append(carry);
    for(int digit : num3){
        sb.append(digit);
    }
    return sb.toString();
 }

References

1 Multiply String and Big Interger 大数乘法加法减法(SegmentFault)