两两相加类总结

两两相加，可以是两个数相加，可以是两个LinkedList Node相加， 也可以是两个binary位相加。。

这类题基本方法是 保留 （sum % 进制）在当前位，然后把 （sum / 进制）作为 进位值向前传递。


两个数相加：通常借用StringBuilder保存结果
415. Add Strings  input把数换成了String，本质就是一位一位相加
989. Add to Array-Form of Integer 一个是array形式，一个是一个数字，本质也是一样
371. Sum of Two Integers 这道题用的bit方法，但本质也是一样，a保存不需要进位的结果，b保存进位的结果，不断循环，直到没有进位（b=0)
43. Multiply Strings 这道题虽然是乘法，本质还是两数相加，只需要注意把数字放在正确的位置上。


两个LinkedList Node相加：通常借用dummy head 保存结果
2. Add Two Numbers  这题LinkedList 是数字从后往前的顺序，比较简单
445. Add Two Numbers II 这题LinkedList 是数字从前往后的顺序，需要借助stack变成从后往前，最后再把结果翻转。


两个binary位相加：通常借用StringBuilder保存结果
67. Add Binary  其他地方跟两个数相加一模一样，只需要把进制从10换成2

43 是个好题, 我很好奇你怎么写的.

大多数人大概是不会用karatsuba写的

337845818 发表于 2019-9-10 22:11
43 是个好题, 我很好奇你怎么写的.

大多数人大概是不会用karatsuba写的

public String multiply(String num1, String num2) {
        if (num1 == null || num2 == null) return "0";
        int[] digits = new int[num1.length() + num2.length()];
        for (int i = num1.length() - 1; i >= 0; i--) {
            for (int j = num2.length() - 1; j >= 0; j--) {
                int product = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int p1 = i + j, p2 = i + j + 1;
                int sum = product + digits[p2];
                digits[p1] += sum / 10;
                digits[p2] = sum % 10;
            }
        }
        StringBuilder res = new StringBuilder();
        for (int digit : digits) {
            if (!(digit == 0 && res.length() == 0)) {
                res.append(digit);
            }
        }
        return res.length() == 0 ? "0" : res.toString();
    }