字符串乘法

43.Multiply Strings

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

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

进位和计算同时进行

按照平常的思维去计算，一边做乘法，一边进行加法进位。

public String multiply(String num1, String num2) {
    int length1 = num1.length();
    int length2 = num2.length();         
    int[] cal = new int[length1 + length2];
    for(int i = length1 - 1; i >= 0; i--){
        for(int j = length2 - 1; j >= 0; j--){
            int p1 = i + j;
            int p2 = i + j + 1;
            int cur = (num1.charAt(i) - '0') * (num2.charAt(j) - '0') + cal[p2];
            cal[p2] = cur % 10;
            cal[p1] += cur/10;
        }
    }
    //转换成字符串
    StringBuilder result = new StringBuilder();
    for(int i: cal){
        if(result.length() != 0 || i != 0 ){
            result.append(String.valueOf(i));
        }
    }

    return result.length() == 0? "0":result.toString();

}

进位和计算分步进行

分步进行的思想实际上运用了进制的思想。采取两步走的策略。首先不如将其看成百进制，之后再将百进制转换为十进制。

对于个位数的乘法，必然结果小于100，即不存在进位。因此首先转换为百进制。

然后对于百进制的转换，说白了就是处理进位。

public String multiply(String num1, String num2) {
    int length1 = num1.length();
    int length2 = num2.length();
    char[] result = new char[length1 + length2];
    int carry = 0;
    
    for(int i = length1 - 1; i >= 0 ; i--){
        for(int j = length2 - 1; j >= 0; j--){
            result[i + j + 1] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
        }
    }
    // 处理进位
    for(int i = result.length - 1; i >= 0; i--){
        result[i] += carry;
        carry = result[i]/10;
        result[i] %= 10;
        result[i] += '0';
    }
    
    //处理字符串前的0
    int begin = 0;
    while(begin < result.length - 1 && result[begin] == '0'){
        begin++;
    }

    return new String(result,begin,result.length - begin);            
    
}