字符串相乘

力扣 43. 字符串相乘

题目说明

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

提示：

num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

示例

示例 1:

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

示例 2:

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

笔者理解

此题是一道字符串算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，我们可以直接模拟数的运算过程，注意额外的进位即可，让我们来看看具体如何实现的吧。

实现

class Solution {
    /**
     * 字符串
     */
    public String multiply(String num1, String num2) {
        // 乘数为 0
        if (Objects.equals(num1, "0") || Objects.equals(num2, "0")) {
            return "0";
        }

        int size1 = num1.length();
        int size2 = num2.length();

        // 两数相乘的位数是 [size1 + size2 - 1, size1 + size2]
        // 例如 10 * 10 = 100
        // 99 * 99 = 9801
        int[] nums = new int [size1 + size2];

        char[] char1 = num1.toCharArray();
        char[] char2 = num2.toCharArray();

        // 翻转，从低位开始计算
        reverse(char1);
        reverse(char2);

        for (int i = 0; i < size1; i++) {
            int now;
            int count = 0;
            // 按位累乘并计算进位
            for (int j = 0; j < size2; j++) {
                now = (char1[i] - '0') * (char2[j] - '0');
                now += nums[i + j];
                now += count;
                count = now / 10;
                now = now % 10;
                nums[i + j] = now;
            }
            // 多余的进位
            int tick = i + size2;
            if (count > 0) {
                now = nums[tick] + count;
                while (now > 9) {
                    count = now / 10;
                    now = now % 10;
                    nums[tick] = now;
                    tick++;
                    now = nums[tick] + count;
                }
                nums[tick] = now;
            }
        }

        StringBuilder result = new StringBuilder();

        int length = nums.length;

        for (int i = 0; i < length - 1; i++) {
            result.append(nums[i]);
        }

        // 预防数组多出来一位的 0
        if (nums[length - 1] != 0) {
            result.append(nums[length - 1]);
        }

        return result.reverse().toString();
    }
    
    /**
     * 翻转
     */
    public void reverse(char[] chars) {
        for (int i = 0; i < chars.length / 2; i++) {
            char temp = chars[i];
            chars[i] = chars[chars.length - 1 - i];
            chars[chars.length - 1 - i] = temp;
        }
    }
}