侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【暴力】字符串相乘

GabrielxD
2022-04-27 / 0 评论 / 0 点赞 / 42 阅读 / 413 字 / 正在检测是否收录...
## 题目

43. 字符串相乘


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

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

示例 1:

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

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

提示:

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

解题

方法一:模拟 竖式相乘

思路

从后向前遍历两个字符串,模拟竖式相乘,把每一位乘起来转为字符串构造器并向后补对应位数的零,然后加和进最终结果(注意要使用字符串加和,否则字符串的位数可能会过大,字符串相加见415. 字符串相加)。

代码

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        char[] num1Arr = num1.toCharArray(), num2Arr = num2.toCharArray();
        int len1 = num1Arr.length, len2 = num2Arr.length;
        String ans = "0";
        for (int i = 0; i < len1; i++) {
            int curr = num1Arr[len1 - 1 - i] - '0';
            for (int j = 0; j < len2; j++) {
                StringBuilder product = new StringBuilder(String
                    .valueOf(curr * (num2Arr[len2 - 1 - j] - '0')));
                for (int k = 0; k < i + j; k++) {
                    product.append("0");
                }
                ans = addStrings(ans, product.toString());
            }
        }
        return ans;
    }

    public String addStrings(String num1, String num2) {
        int idx1 = num1.length(), idx2 = num2.length();
        StringBuilder ans = new StringBuilder();
        int carry = 0;
        while(--idx1 >= 0 | --idx2 >= 0 || carry != 0) {
            int digit1 = idx1 >= 0 ? num1.charAt(idx1) - '0' : 0;
            int digit2 = idx2 >= 0 ? num2.charAt(idx2) - '0' : 0;
            int currDigit = carry + digit1 + digit2;
            carry = currDigit / 10;
            ans.append(currDigit % 10);
        }
        return ans.reverse().toString();
    }
}
0

评论区