LeetCode43(字符串相乘)

题目：

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

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

示例 2:
输入: num1 = "123", num2 = "456"a
输出: "56088"

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

解题思路

1. 先算num1和num2的长度
2. 两数相乘，最大长度为2个值的长度和，所以创建一个数组，长度为两个字符串的长度和
3. 从num2的个位开始，依次和num1的每一位相乘，个位的位置为i+j+1，进位的位置为i+j，将个位和进位依次放入数组，个位是相乘的结果加上要放入的位置的值的和的个位，进位的位置是在原数据的基础上加上进位的值。最后输出字符串

解题例子

789 * 256
数值：num1 = 789， num2 = 256
长度：n1 = 3，n2 = 3
相乘之后的答案的长度最大为6，所以，数组result[]长度为6

从256的最后一位开始，也就是6

j = 2，i = 2，那么个位位置为p2 = i + j + 1= 5，进位位置为p1 = i + j = 4 ， 6 * 9 + 0= 54 ，result = [ , , , ,5,4]

j = 2，i = 1，那么个位位置为p2 = i + j + 1= 4，进位位置为p1 = i + j = 3 ， 6 * 8 + 5 = 53 ，result = [ , , ,5,3,4]

j = 2，i = 0，那么个位位置为p2 = i + j + 1= 3，进位位置为p1 = i + j = 2 ， 6 * 7 + 5 = 47 ，result = [ , ,4,7,3,4]

j = 1，i = 2，那么个位位置为p2 = i + j + 1= 4，进位位置为p1 = i + j = 3 ， 5 * 9 + 3 = 48 ，result = [ , ,4,11,8,4]

j = 1，i = 1，那么个位位置为p2 = i + j + 1= 3，进位位置为p1 = i + j = 2 ， 5 * 8 + 11 = 51 ，result = [ , ,9,1,8,4]

j = 1，i = 0，那么个位位置为p2 = i + j + 1= 2，进位位置为p1 = i + j = 1 ， 5 * 7 + 9 = 44 ，result = [ ,4,4,1,8,4]

j = 0，i = 2，那么个位位置为p2 = i + j + 1= 3，进位位置为p1 = i + j = 2 ， 2 * 9 + 1 = 19 ，result = [ ,4,5,9,8,4]

j = 0，i = 1，那么个位位置为p2 = i + j + 1= 2，进位位置为p1 = i + j = 1 ， 2 * 8 + 5 = 21 ，result = [ ,6,1,9,8,4]

j = 0，i = 0，那么个位位置为p2 = i + j + 1= 1，进位位置为p1 = i + j = 0 ， 2 * 7 + 6 = 20 ，result = [2,0,1,9,8,4]

最终结果是201984

代码实现

class FourthSolution {
    public String multiply(String num1, String num2) {
        if (num1 == null || num1.length() == 0 || num2 == null || num2.length() == 0) {
            return "";
        }
        int n1 = num1.length();
        int n2 = num2.length();
        if (n1 == 1 && Integer.parseInt(num1) == 0) {
            return num1;
        }
        if (n2 == 1 && Integer.parseInt(num2) == 0) {
            return num2;
        }

        int result[] = new int[n1 + n2];

        for (int j = n2 - 1; j >= 0; j--) {
            for (int i = n1 - 1; i >= 0; i--) {
                int p1 = i + j; //每次 num2.charAt(j) * num1.charAt(i)的值的进位的位置
                int p2 = i + j + 1; //每次 num2.charAt(j) * num1.charAt(i)的值的个位位置
                int sum = (num2.charAt(j) - '0') * (num1.charAt(i) - '0') + result[p2];
                result[p2] = sum % 10; //当前值的个位数字
                result[p1] += sum / 10;//加上进位的值

            }
        }
        StringBuilder finalResult = new StringBuilder();
        for (int num : result) {
            if (num == 0 && finalResult.length() == 0) {
                continue;
            }
            finalResult.append(num);
        }

        return finalResult.length() == 0 ? "0" : finalResult.toString();
    }

}

public class ByteDanceFourth {
    public static void main(String[] args) {
        System.out.println("请输入第一个字符串：");
        Scanner scanner1 = new Scanner(System.in);
        String num1 = scanner1.next();

        System.out.println("请输入第二个字符串：");
        Scanner scanner2 = new Scanner(System.in);
        String num2 = scanner2.next();

        String x = new FourthSolution().multiply(num1, num2);
        System.out.println(x);

    }
}