Loading...
首页 计算机 算法 算法题 中等

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

提示：

  • 1 <= num1.length, num2.length <= 200
  • num1 和 num2 只能由数字组成。
  • num1 和 num2 都不包含任何前导零，除了数字 0 本身。

解法

/**
 * 456*123
 * 进位 carry = 0
 * 第五位：6 * 3 + carry =                  8......1 (更新 carry = 1)
 * 第四位：5 * 3 + 6 * 2 + carry =          8......2 (更新 carry = 2)
 * 第三位：4 * 3 + 5 * 2 + 6 * 1 + carry =  0......3 (更新 carry = 3)
 * 第二位：4 * 2 + 5 * 1 + carry =          6......1 (更新 carry = 1)
 * 第一位：4 * 1 + carry =                  5......0 (更新 carry = 0)
 * 如果 carry!=1，将 carry 再放前一位、
 * 结果为 56088
 *
 * 对应下标：
 * i2 * j2
 * i1 * j2 + i2 * j1
 * i0 * j2 + i1 * j1 + i2 * j0
 * i0 * j1 + i1 * j0
 * i0 * j0
 *
 * @param num1
 * @param num2
 * @return
 */
public String mulity(String num1, String num2) {
    if ("0".equals(num1) || "0".equals(num2)){
        return "0";
    }
    int[] s1 = toIntArray(num1);
    int[] s2 = toIntArray(num2);
    int i = s1.length - 1;
    int j = s2.length - 1;
    String s = "";
    int carry = 0;
    for (int k = 0; k < s1.length + s2.length - 1; k++){
        int m = j;
        int sum = 0;
        // 循环次数（1,2,3,2,1）
        for (int l = i; i == 0 ? l <= j : l <= s1.length - 1; l++){
            sum = sum + (l >= s1.length ? 0 : s1[l]) * (m >= 0 ? s2[m--] : 0);
        }
        sum = sum + carry;
        carry = sum / 10;
        s = (sum % 10) + s;
        if (i == 0 && j > 0){
            j--;
        }
        if (i > 0){
            i--;
        }
    }
    return carry == 0 ? s : carry + s;
}
优化
public String mulity(String num1, String num2) {
    if ("0".equals(num1) || "0".equals(num2)){
        return "0";
    }
    int num1Length = num1.length();
    int num2Length = num2.length();
    int[] result = new int[num1Length + num2Length];
    for (int i = num1.length() - 1; i >= 0; i--){
        int a = num1.charAt(i) - '0';
        for (int j = num2.length() - 1; j >= 0; j--){
            int b = num2.charAt(j) - '0';
            // 求和
            int sum = result[i + j + 1] + a * b;
            // 当前位置取余数
            result[i + j + 1] = sum % 10;
            // 前一个位置取进位值
            result[i + j] = result[i + j] + sum / 10;
        }
    }
    // 第一个可能存在 0 的情况，去除
    StringBuilder s = new StringBuilder();
    for (int i = 0; i < result.length; i++){
        if (i == 0 && result[0] == 0){
            continue;
        }
        s.append(result[i]);
    }
    return s.toString();
}