43. 字符串相乘

题目描述

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

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

输入输出

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

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

基本思路

可参考 415. 字符串相加 的思路 参照代码注释不难理解 就是很麻烦(泪

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    public String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0")){
            return "0";
        }
        // 保存计算结果
        String res = "0";
        // num2 逐位与 num1 相乘
        for(int i = num2.length() - 1; i >= 0; i--){
            int flag = 0;
            // 保存 num2 第i位数字与 num1 相乘的结果
            StringBuilder sb = new StringBuilder();
            for(int j = 0; j < num2.length() - i - 1; j++){
                // num2 除了第一位的其他位与 num1 运算的结果需要 补0
                //例如123*456 当123*5时 最后一位必须补0变成6150
                sb.append(0);
            }
            int n2 = num2.charAt(i) - '0';
            // num2 的第 i 位数字 n2 与 num1 相乘
            // flag指进位数 例如4*6 flag就为2
            for(int j = num1.length() - 1; j >= 0 || flag != 0; j--){
                int n1 = j < 0 ? 0 : num1.charAt(j) - '0';
                int product = (n1 * n2 + flag) % 10;
                sb.append(product);
                flag = (n1 * n2 + flag) / 10;
            }
            res = addStrings(res, sb.reverse().toString());
        }
        return res;
    }

    public String addStrings(String num1, String num2) {
        // 对两个字符串进行相加 leetcode-415
        int i = num1.length() - 1, j = num2.length() - 1, flag = 0;
        StringBuffer sb = new StringBuffer("");
        while(i >= 0 || j >= 0){
            int n1 = i >= 0? num1.charAt(i) - '0': 0;
            int n2 = j >= 0? num2.charAt(j) - '0': 0;
            int tmp = n1 + n2 + flag;
            flag = tmp / 10;
            sb.append(tmp%10);
            i--;j--;
        }
        if(flag == 1) sb.append(1);
        return sb.reverse().toString();
    }
}