1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length(), n = num2.length();
        int[] product = new int[m + n];
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int pos1 = i + j + 1, pos2 = i + j;
                int multiple = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int sum = multiple + product[pos1];
                product[pos1] = sum % 10;
                product[pos2] += sum / 10;
            }
        }
        StringBuilder ans = new StringBuilder();
        for (int digit : product) {
            if (!(ans.length() == 0 && digit == 0)) {
                ans.append(digit);
            }
        }
        return ans.length() == 0 ? "0" : ans.toString();
    }
}

这道题就是考察如何乘两个数字.

关键的一点就是两数相乘, 最长就是m + n, m和n分别是两个数字的长度. 还有就是两个位相乘, 它们应该加在答案中的哪个位或者哪两个位上. 答案就是i + j + 1和i + j这两个位. 因为比如说num1的最后一位和num2的最后一位相乘, 应该放在结果的最后一位和倒数第二位. num1或者num2如果减小1, 那么相应地, 结果应该放在的两位也会各自减小1. 当num1是m - 1, num2是n - 1时, 答案应该放在m + n - 1和m + n - 2处, 那也就是i + j + 1处和i + j处. 因此这就是对应关系.

简单来说让num1和num2所有位两两相乘, 并把结果加到对应的两个位上.

有个小细节需要注意, 我们发现我们得到multiply后, 我们把这个数字和在product[i + j + 1]的数字相加. 这很好理解. 因为我们要把multiply放到i + j + 1和i + j这两位上. 先和i + j + 1相加, 这样如果有进位可以及时得到. 但是问题来了, 如果i + j这个位得到进位后刚好也要进位呢? 这不需要担心, 这在我们考虑i + j和i + j - 1的时候就会考虑到. 那么所有位的进位都会被考虑到除了最左边那一位, 这一位无论如何不会进位. 因为我们之前说明长度为m的数字乘上长度为n的数字, 答案最长为m + n. 因此最左边一位虽然没有被考虑到, 但是它必不可能进位.

时间复杂度: O(m * n) 两个数字任意两位的组合都要考虑.
空间复杂度: O(m + n) 我们声明了一个数组来装答案.