随笔记录

算法-43.字符串相乘

2022-3-22 diaba 算法

package com.jiucaiyuan.net.question;

/**
 * @Author jiucaiyuan  2022/3/22 21:59
 * @mail services@jiucaiyuan.net
 */

public class TwoStrMultiply {
    /**
     * v2 leeCode上学的，确实方法好
     * https://leetcode-cn.com/problems/multiply-strings/solution/zi-fu-chuan-xiang-cheng-by-leetcode-solution/
     *
     * 方法一的做法是从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次得到的结果累加，
     * 整个过程中涉及到较多字符串相加的操作。如果使用数组代替字符串存储结果，则可以减少对字符串的操作。
     * 令 m 和 n 分别表示 num1和 num2的长度，并且它们均不为 0，则 num1 和 num2 的乘积的长度为
     * m+n−1 或 m+n。简单证明如下：
     *
     * case1 如果 num1和 num2都取最小值，则 num1=10^(m−1)，num2=10^(n−1)，
     *      num1×num2=10^(m+n−2) ，乘积的长度为 m+n-1;
     * case2 如果 num1 和 num2都取最大值，则 num1=10^m − 1, num2=10^n − 1 ，
     *      num1×num2 =10^(m+n) − 10^m − 10^n + 1， 乘积显然小于 10^(m+n)且大于 10^(m+n-1) ，
     *      因此乘积的长度为 m+nm+n。
     *
     * 由于 num1 和 num2的乘积的最大长度为 m+n，因此创建长度为 m+n 的数组 ansArr 用于存储乘积。
     * 对于任意 0≤i<m 和 0≤j<n，num1[i] * num2[j] 的结果位于 ansArr[i+j+1]，
     * 如果 ansArr[i+j+1]≥10，则将进位部分加到 ansArr[i+j]。
     * 最后，将数组 ansArr 转成字符串，如果最高位是 00 则舍弃最高位。
     *
     * @param num1
     * @param num2
     * @return
     */
    public static String multiply2(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        int m = num1.length();
        int n = num2.length();
        //存放结果
        int[] ansArr = new int[m + n];
        for (int i = m - 1; i >= 0; i--) {
            int x = num1.charAt(i) - '0';
            for (int j = n - 1; j >= 0; j--) {
                int y = num2.charAt(j) - '0';
                //num1[i] * num2[j] 的结果位于 ansArr[i+j+1]
                ansArr[i + j + 1] += x * y;
            }
        }
        //逐个检查，有大于10的，处理进位
        for (int i = m + n - 1; i > 0; i--) {
            ansArr[i - 1] += ansArr[i] / 10;
            ansArr[i] %= 10;
        }
        //如果第一位是0，则舍弃
        int index = ansArr[0] == 0 ? 1 : 0;
        StringBuffer ans = new StringBuffer();
        while (index < m + n) {
            ans.append(ansArr[index]);
            index++;
        }
        return ans.toString();
    }

    /**
     * v1  数字太大会越界
     * @param num1
     * @param num2
     * @return
     */
    public static String multiply(String num1, String num2) {
        int result = 0;
        if (num1.equals("0") || num2.equals("0")) {
            return String.valueOf(result);
        }
        char[] str1Arr = num1.toCharArray();
        char[] str2Arr = num2.toCharArray();
        int weight1 = 1;
        for (int i = str1Arr.length - 1; i >= 0; i--) {
            if(i != str1Arr.length - 1 ){
                weight1 *= 10;
            }
            int weight2 = 1;
            for (int j = str2Arr.length - 1; j >= 0; j--) {
                if(j != str2Arr.length - 1 ){
                    weight2 *= 10;
                }
                int product = ((str1Arr[i] - '0') * (str2Arr[j] - '0'));
                int weight = weight1 * weight2;
                result += weight * (product % 10) + (product / 10) * weight * 10;
            }
        }
        return String.valueOf(result);

    }

    public static void main(String[] args) {
        String str2 = "123";
        String str1 = "3";
        System.out.println(multiply(str1, str2));
        str2 = "200";
        str1 = "200";
        System.out.println(multiply(str1, str2));
        str2 = "21";
        str1 = "21";
        System.out.println(multiply(str1, str2));
        str2 = "210";
        str1 = "210";
        System.out.println(multiply(str1, str2));
        str2 = "456";
        str1 = "654";
        System.out.println(multiply(str1, str2));
        str2 = "5102381023812";
        str1 = "200123123";
        System.out.println(multiply(str1, str2));
        System.out.println(multiply2(str1, str2));
    }
}