字符串相乘

LeetCode每日一题，43. Multiply Strings

先看题目描述

大意是两个大整数以字符串形式给出，让我们返回两数相乘后的结果，要求不能使用大整数类

算法和思路

做加法

这是自己实现的，思路就是模拟竖式乘法，从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次得到的结果累加，在累加时需要注意，乘数除了最低位外，其余每一位的运算结果都需要补 0

做乘法

这是看题解才理解的方法，效率明显优于做加法。由于 num 1和 num 2 的乘积的最大长度为 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]

算法源码

做加法

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.length() < num2.length()) return multiply(num2, num1);
        int m = num1.length();
        int n = num2.length();
        if (n == 1) return singleMultiply(num1, num2.charAt(0)).toString();
        StringBuilder temp = new StringBuilder("0");
        for (int i = 1; i <= n; i++) {
            StringBuilder cur = singleMultiply(num1, num2.charAt(n - i));
            for (int j = 1; j < i; j++) {
                cur.append(0);
            }
            temp = add(cur, temp);
        }
        return temp.toString();
    }

    public StringBuilder singleMultiply(String num1, char num2) {
        if (num2 == '0') return new StringBuilder("0");
        StringBuilder res = new StringBuilder();
        int carry = 0;
        int num = (int)(num2 - '0');
        for (int i = num1.length() - 1; i >= 0; i--) {
            int temp = (num1.charAt(i) - '0') * num + carry;
            res.append(temp % 10);
            carry = temp / 10;
        }
        if (carry > 0) res.append(carry);
        return res.reverse();
    }

    public StringBuilder add(StringBuilder num1, StringBuilder num2) {
        StringBuilder res = new StringBuilder();
        int m = num1.length();
        int n = num2.length();
        int len = Math.max(m, n);
        int carry = 0;
        for (int i = 1; i <= len; i++) {
            int n1 = m - i >= 0 ? (num1.charAt(m - i) - '0') : 0;
            int n2 = n - i >= 0 ? (num2.charAt(n - i) - '0') : 0;
            int temp = n1 + n2 + carry;
            res.append(temp % 10);
            carry = temp / 10;

        }
        if (carry > 0 ) res.append(carry);
        return res.reverse();
    }
}

做乘法

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        int m = num1.length(), 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';
                ansArr[i + j + 1] += x * y;
            }
        }
        for (int i = m + n - 1; i > 0; i--) {
            ansArr[i - 1] += ansArr[i] / 10;
            ansArr[i] %= 10;
        }
        int index = ansArr[0] == 0 ? 1 : 0;
        StringBuffer ans = new StringBuffer();
        while (index < m + n) {
            ans.append(ansArr[index]);
            index++;
        }
        return ans.toString();
    }
}