力扣43字符串相乘笔记

力扣43.字符串相乘

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

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

示例 1:

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

示例 2:

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/multiply-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

刚开始时，是我想简单了，没有考虑到整数范围会溢出，导致最后有一堆特别长的相乘根本过不去

class Solution {
    public String multiply(String num1, String num2) {
        long sum1 = si(num1);
        long sum2 = si(num2);
        long x = sum1*sum2;
        String s = x+"";
        return s;
    }
    public static int si(String s){
        int sum = 0;
        for(int i=0;i<s.length();i++){
            int a = s.charAt(i)-48;
            sum = a+sum*10;

        }
        return sum;
    }
}

这里数据类型由一开始的int到long，最后还是过不去，后面的例子长度超过了long的范围，可是题目要求不能用内置的BigInteger库，所以这个方法最后废弃了。

于是开始看题解，发现这题远比想的要难，找到一个最优解---优化竖式法，这里面体现了数学思想。

该算法是通过两数相乘时，乘数某位与被乘数某位相乘，与产生结果的位置的规律来完成。具体规律如下：

    乘数 num1 位数为 M，被乘数 num2 位数为 N， num1 x num2 结果 res 最大总位数为 M+N
    num1[i] x num2[j] 的结果为 tmp(位数为两位，"0x","xy"的形式)，其第一位位于 res[i+j]，第二位位于 res[i+j+1]。

这里附上题解带的图

相同位数的数相乘，其结果的最大位数只能是这一位或这一位并包括再进一位，同理， 也就是上面的i+j或i+j+1

代码

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }//先判断一下，如果其中有一个为0，那么可以不用管了，直接退出
        int[] res = new int[num1.length() + num2.length()];
        //上面我们已经得知最大总位数是M+N，即两个数字位数之和，这里就直接明确了新数组的位数
        for (int i = num1.length() - 1; i >= 0; i--) {
            //从个位数开始遍历
            int n1 = num1.charAt(i) - '0';//每个字符要减去’0‘才能是实际数字大小
            for (int j = num2.length() - 1; j >= 0; j--) {
                int n2 = num2.charAt(j) - '0';
                int sum = (res[i + j + 1] + n1 * n2);
                /*sum为第一个数的一位与第二个数的一位相乘的结果再加上上一次的乘积的余数*/
                res[i + j + 1] = sum % 10;
                res[i + j] += sum / 10;//新数组每一位便是每一次sum的最高位
            }
        }

        StringBuilder result = new StringBuilder();
        for (int i = 0; i < res.length; i++) {
            if (i == 0 && res[i] == 0) continue;
            result.append(res[i]);
            //将结果中每一位的元素添加到新数组中
        }
        return result.toString();
    }
}