2022.07.15_每日一题

43. 字符串相乘

题目描述

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

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

 

示例 1:

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

示例 2:

输入: num1 = “123”, num2 = “456”
输出: “56088”

 

提示：

• 1 <= num1.length, num2.length <= 200
• num1 和 num2 只能由数字组成。
• num1 和 num2 都不包含任何前导零，除了数字0本身。

Related Topics

• 数学
• 字符串
• 模拟

coding

class Solution {
    
    public String multiply(String num1, String num2) {
    

        // 会超范围
        // Integer n1 = Integer.valueOf(num1);
        // Integer n2 = Integer.valueOf(num2);
        // return n1 * n2 + "";

        // BigDecimal yyds!! 哈哈哈
        // BigDecimal s1 = new BigDecimal(num1);
        // BigDecimal s2 = new BigDecimal(num2);
        // return s1.multiply(s2).toString();

        // 模拟
        // 如果其中一个数是 "0", 则结果必定为 "0"
        if (num1.equals("0") || num2.equals("0")) {
    
            return "0";
        }
        String res = "";
        Stack<String> stack = new Stack();
        int temp = 0;
        for (int i = num1.length() - 1; i >= 0; i--) {
    
            for (int j = num2.length() - 1; j >= 0; j--) {
    
                stack.add(String.valueOf((Integer.parseInt(num1.substring(i, i + 1)) * Integer.parseInt(num2.substring(j, j + 1)) + temp) % 10));
                temp = (Integer.parseInt(num1.substring(i, i + 1)) * Integer.parseInt(num2.substring(j, j + 1)) + temp) / 10;
            }
            if (temp != 0) {
    
                stack.add(String.valueOf(temp));
                temp = 0;
            }
            StringBuffer str = new StringBuffer(stack.size());
            while (!stack.isEmpty()) {
    
                str.append(stack.pop());
            }
            int zeroCnt = num1.length() - 1 - i;
            while (zeroCnt > 0) {
    
                str.append('0');
                zeroCnt --;
            }
            res = addStr(res, str.toString());
        }
        return res;
    }

    private String addStr(String str1, String str2) {
    
        StringBuffer sum = new StringBuffer();
        int temp = 0;
        Stack<String> stack = new Stack();
        int index1 = str1.length() - 1;
        int index2 = str2.length() - 1;
        while (index1 >= 0 || index2 >= 0) {
    
            int num1 = 0;
            int num2 = 0;
            if (index1 >= 0) {
    
                num1 = Integer.parseInt(str1.substring(index1, index1 + 1));
            }
            if (index2 >= 0) {
    
                num2 = Integer.parseInt(str2.substring(index2, index2 + 1));
            }
            stack.add(String.valueOf((num1 + num2 + temp) % 10));
            temp = (num1 + num2 + temp) / 10;
            index1 --;
            index2 --;
        }
        if (temp != 0) {
    
            stack.add(String.valueOf(temp));
        }
        while (!stack.isEmpty()) {
    
            sum.append(stack.pop());
        }
        return sum.toString();
    }
}