leetcode-字符串相乘

发表于

8月每日在leetcode至少做一题，9月份开始有点懈怠了，希望可以继续保持吧。每天学习和进步一点，才能保持感觉，对算法的应用场景上，嗅觉也会更灵敏一点点，有合适的场景就能用起来，毕竟解决了实际的问题，算法才提现价值。

今天做的是leetcode的第43题，题目比较水，也没什么算法的思想，就当练练编程基础吧。

题目

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

示例 1:

输入: num1 = “2”, num2 = “3”

输出: “6”

示例 2:

输入: num1 = “123”, num2 = “456”

输出: “56088”

说明：

num1 和 num2 的长度小于110。

num1 和 num2 只包含数字 0-9。

num1 和 num2 均不以零开头，除非是数字 0 本身。

不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

思路

看到说明里面的最后一条，我差点笑出声，其实很多年之前在学校刷题的时候也做过类似的，我们有个同学就是靠java的BigDecimal过的。当然这样过就失去意义了，我们还是探寻一下一般的解法。

回到小学的多位数相乘，其实就是把其中一个数字逐位拆开，与另外一个数去相乘，然后再把和相加。这样就从多位数乘法简化成了一位数乘以多位数；然后进一步简化成一位数乘以一位数再相加。

我们现在用程序来解，就是模拟了这个过程，如下图所示
43.png

当然，这道题目做的过程中也有一些注意点：

1、注意补零，逐位相乘的时候，高位数去做乘法时，后面是要补零的，如上图的竖式所示

2、数字可能很长，中间的结果也要用数组表示，用整数的话可能会溢出

3、虽然原字符串遍历完了，但是可能还有从低位进位上来的数组，别丢了

所以，本题还需要一个隐含的函数，就是2个字符串类型的数字相加，这其实就是leetcode第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
48
49
50
51
52
53
54
55
56
ini复制代码class Solution {
    public String multiply(String num1, String num2) {
        String ans = "0";
        if ("0".equals(num1) || "0".equals(num2)) {
            return ans;
        }
        int len1 = num1.length();
        int len2 = num2.length();
        for (int i = len2 - 1; i >= 0; i--) {
            int adddition = 0;
            int n2 = num2.charAt(i) - '0';
            StringBuilder temp = new StringBuilder();
            // 因为temp是倒过来的，所以需要先补零
            int need = len2 - 1 - i;
            while (need-- > 0) {
                temp.append("0");
            }
            for (int j = len1 - 1; j >= 0; j--) {
                int n1 = num1.charAt(j) - '0';
                int num = n2 * n1 + adddition;
                temp.append(num % 10);
                adddition = num / 10;
            }
            if (adddition > 0) {
                temp.append(adddition);
            }
            ans = addStrings(ans, temp.reverse().toString());
        }
        return ans;
    }

    public static String addStrings(String num1, String num2) {
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        // 进位
        int adddition = 0;
        StringBuilder ans = new StringBuilder();
        while (i >=0 || j >=0 || adddition > 0) {
            int temp = 0;
            if (i >= 0) {
                temp += num1.charAt(i) - '0';
                i--;
            }
            if (j >= 0) {
                temp += num2.charAt(j) - '0';
                j--;
            }
            if (adddition > 0) {
                temp += adddition;
            }
            ans.append(temp % 10);
            adddition = temp / 10;
        }
        return ans.reverse().toString();
    }
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%