43. 字符串相乘

https://leetcode-cn.com/problems/multiply-strings/

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        int length_1 = num1.length();
        int length_2 = num2.length();
        int[] res = new int[length_1 + length_2];
        for (int i = length_1 - 1; i >= 0; i--) {
            // 对循环里的每次遍历，需要先将字符转为数字
            int n_1 = num1.charAt(i) - '0';
            for (int j = length_2 - 1; j >= 0; j--) {
                // 对循环里的每次遍历，需要先将字符转为数字
                int n_2 = num2.charAt(j) - '0';
                // 从结果数组的末尾开始往前计算，需要处理进位
                // 计算相乘的结果，还有可能的进位
                int sum = res[i + j + 1] + n_1 * n_2;
                // 进位处理
                res[i + j + 1] = sum % 10;
                // 这里的处理是：进位加上原先值，用于上上行再下一轮加和使用
                // 还需要补充一下，没有这一步，就体现不出累加的概念，也就模拟不出竖式计算
                res[i + j] += sum / 10;
            }
        }
        StringBuffer resBuffer = new StringBuffer();
        for (int i = 0; i < length_1 + length_2; i++) {
            if (i == 0 && res[i] == 0) continue;
            resBuffer.append(res[i]);
        }
        return resBuffer.toString();
    }
}

class Solution {
    public String multiply(String num1, String num2) {
        if ("0".equals(num1) || "0".equals(num2)) {
            return "0";
        }
        int[] resArray = new int[num1.length() + num2.length()];
        // 遍历每一位
        for (int i = num1.length() - 1; i >= 0; i--) {
            int n1 = num1.charAt(i) - '0';
            for (int j = num2.length() - 1; j >= 0; j--) {
                int n2 = num2.charAt(j) - '0';
                // 计算乘积
                int product = n1 * n2;
                // 保存至结果数组
                int sum = product + resArray[i + j + 1];
                // 重新更新，叠加结果的个位保存至数组的 i + j + 1 的位置
                resArray[i + j + 1] = sum % 10;
                // 个位保存至数组的 i + j 的位置
                resArray[i + j] += sum / 10;
            }
        }
        // 将结果数组转为 string
        StringBuilder builder = new StringBuilder();
        // 收尾是否为 0，是的话就跳过，不是就遍历
        int start = resArray[0] == 0 ? 1 : 0;
        for (int i = start; i < resArray.length; i++) {
            builder.append(resArray[i]);
        }
        return builder.toString();
    }
}

class Solution {
    public String multiply(String num1, String num2) {
        if ("0".equals(num1) || "0".equals(num2)) {
            return "0";
        }
        // 定义输出结果，直接定义成 string，调用字符串相加
        String res = "0";
        // 从个位开始，遍历 num2 的每一位，跟 num1 相乘
        for (int i = num2.length() - 1; i >= 0; i--) {
            // 取出 num2 的当前数位，作为当前乘法的第二个乘数
            int n2 = num2.charAt(i) - '0';
            StringBuilder curResult = new StringBuilder();
            int carry = 0;
            // 因为结果是倒序，所以当前 n2 对应数位要补零，
            // 应该先写入 curResult，补充 n - 1 - i 个零
            for (int j = 0; j < num2.length() - 1 - i; j++) {
                curResult.append("0");
            }
            // 遍历 num1 中的每一位
            for (int j = num1.length() - 1; j >= 0; j--) {
                // 提取 num1 的当前数位，作为当前乘法的第一个乘数
                int n1 = num1.charAt(j) - '0';
                // 计算当前结果
                int product = n1 * n2 + carry;
                // 保存
                curResult.append(product % 10);
                carry = product / 10;
            }
            // 所有位数乘法计算完毕，如果有进位，需要将进位单独作为一位保存下来
            if (carry != 0) {
                curResult.append(carry);
            }
            // 此时得到的就是 num1 和 num2 中当前位 n2 的最终乘积
            // 将当前乘积叠加
            res = new AddStrings().addStrings(res, curResult.reverse().toString());
        }
        return res;
    }
}
class AddStrings {
    public String addStrings(String num1, String num2) {
        // 思路：每一位分别叠加，结果放入字符串，最后倒叙。需要来考虑进位的问题
        StringBuffer res = new StringBuffer();
        // 定义遍历 2 个字符串的初始位置
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        // 定义进位变量
        int carry = 0;
        // 统一进位情况：只要未遍历完或者还有进位，就补零继续
        while (i >= 0 || j >= 0 || carry != 0) {
            // 取两数当前的对应数位，但是取出来可能不是数字，也就是没有数字了，要补零站位
            // 字符要将 ASCII 码转为数字
            int n1 = i >= 0 ? num1.charAt(i) - '0' : 0;
            int n2 = j >= 0 ? num2.charAt(j) - '0' : 0;
            // 对当前数位求和
            int sum = n1 + n2 + carry;
            res.append(sum % 10);
            carry = sum / 10;
            // 移动指针，遍历下一位
            i--;
            j--;
        }
        return res.reverse().toString();
    }
}