描述

题目描述

以字符串的形式读入两个数字，编写一个函数计算它们的乘积，以字符串形式返回。

（字符串长度不大于10000，保证字符串仅由'0'~'9'这10种字符组成）

示例

输入："11","99"
返回值："1089"
说明：11*99=1089  

引言

类似这种貌似没有算法套路的题目，应该在纸上画图、推算，得出规律

知识点：模拟，分治
难度：⭐⭐⭐

题解

解题思路

通过分治的思想，先将输入的两个大数转化成整型数组存储，接着通过两个整型数组逐位相乘后，处理进位，得出结果

方法一：分治

图解

算法流程：

• 将两个字符串转化为整型数组形式
• 逐位相乘，中间 i * j 会有重复出现，如89 * 12, 会有res = [0, 81, 82+91, 92]
• 从最低位，也就是数组res最右边元素开始处理进位
• 接着从最高位开始收集结果即可

Java 版本代码如下：

import java.util.*;
public class Solution {
    public String solve (String s, String t) {
        //将字符串转化为数组形式
        int lenS = s.length(), lenT = t.length();
        int[] arrS = new int[lenS];
        int[] arrT = new int[lenT];
        for(int i = 0; i < lenS; i++) {
            arrS[i] = s.charAt(i) - '0';
        }
        for(int i = 0; i < lenT; i++) {
            arrT[i] = t.charAt(i) - '0';
        }
        // 存放结果
        int[] res = new int[lenS + lenT];
        // 中间 i * j 会有重复出现，如89 * 12, 会有res = [0, 8*1, 8*2+9*1, 9*2]
        for(int i = 0; i < lenS; i++) {
            for(int j = 0; j < lenT; j++) {
                // i + j + 1 是为了给进位留一个位置
                res[i + j + 1] += arrS[i] * arrT[j];
            }
        }
        // 进位的值
        int carry = 0;
        // 从最低位，也就是数组res最右边元素开始处理进位
        for(int i = lenS + lenT - 1; i >= 0; i--) {
            res[i] += carry;
            carry = res[i] / 10;
            res[i] = res[i] % 10;
        }
        StringBuilder ans = new StringBuilder();
        // 表示当前位在数组的索引，目的是找出高位的0的位置，前置的0需要忽略掉
        int cur = 0;
        while(cur < lenS + lenT && res[cur] == 0) {
            cur++;
        }
        // 收集结果
        for(int i = cur; i < res.length; i++) {
            ans.append(res[i]);
        }
        return ans.length() == 0 ? "0" : ans.toString();
    }
}

复杂度分析：

时间复杂度 O(MN)：需要遍历两个字符串的每个字符，M和N分别为两个字符串的长度
空间复杂度 O(N)：需要借助数组保存中间结果以及最终结果