题目描述

给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和。

注意:

num1 和num2 的长度都小于 5100.
num1 和num2 都只包含数字 0-9.
num1 和num2 都不包含任何前导零。
你不能使用任何內建 BigInteger 库, 也不能直接将输入的字符串转换为整数形式。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/add-strings
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解决方法-竖式运算

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        int[] res = new int[num1.length() + num2.length()];
        for (int i = num1.length() - 1; i >= 0; i--) {
            int n1 = num1.charAt(i) - '0';
            for (int j = num2.length() - 1; j >= 0; j--) {
                int n2 = num2.charAt(j) - '0';
                int sum = (res[i + j + 1] + n1 * n2);
                //进位处理
                res[i + j + 1] = sum % 10;
                //求出当前位的值
                res[i + j] += sum / 10;
            }
        }

        StringBuilder result = new StringBuilder();
        for (int i = 0; i < res.length; i++) {
            if (i == 0 && res[i] == 0) continue;
            result.append(res[i]);
        }
        return result.toString();
    }
}

作者:breezean
链接:https://leetcode-cn.com/problems/multiply-strings/solution/you-hua-ban-shu-shi-da-bai-994-by-breezean/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

  • 时间复杂度:$O(n^2)$

解决方法-Karatsuba乘法

karatsuba


最后的结果就是 $x∗y=a∗c∗10n+(a ∗ d + b ∗ c)∗10{n/2}+bd$

比如12345*6789,那么a=12,b=345,c=6,d=789

 /**
 * Karatsuba乘法
 */
public static long karatsuba(long num1, long num2){
    //递归终止条件
    if(num1 < 10 || num2 < 10) return num1 * num2;
    // 计算拆分长度
    int size1 = String.valueOf(num1).length();
    int size2 = String.valueOf(num2).length();
    int halfN = Math.max(size1, size2) / 2;
    /* 拆分为a, b, c, d */
    long a = Long.valueOf(String.valueOf(num1).substring(0, size1 - halfN));
    long b = Long.valueOf(String.valueOf(num1).substring(size1 - halfN));
    long c = Long.valueOf(String.valueOf(num2).substring(0, size2 - halfN));
    long d = Long.valueOf(String.valueOf(num2).substring(size2 - halfN));
    // 计算z2, z0, z1, 此处的乘法使用递归
    long z2 = karatsuba(a, c);
    long z0 = karatsuba(b, d);
    long z1 = karatsuba((a + b), (c + d)) - z0 - z2;
    return (long)(z2 * Math.pow(10, (2*halfN)) + z1 * Math.pow(10, halfN) + z0);
}
  • 时间复杂度:$ O(n^{log_2 3}) $

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

人生中没有四季 唯有那寒冬的荒野