leetcode|中等:43. 字符串相乘

1.题目

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

示例 1:

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

示例 2:

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

提示：

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

2. 题解

2.1 思路分析

思路1：题目比较简单 分析乘法运算过程并手动进行模拟即可

2.2 代码实现

• 思路1：手动模拟乘法计算过程

import java.util.Arrays;

class Solution {
    public String multiply(String num1, String num2) {
        if(num1.equals("0")||num2.equals("0")){
            return "0";
        }

        // 计算res的最大可能长度
        int maxResLen = num1.length()*num2.length()+2;

        int[] res = new int[maxResLen];
        for (int i = 0; i < maxResLen; i++) {
            res[i] = 0;
        }

        // String num1 --> num1BitList
        int[] num1BitList = new int[num1.length()];
        for (int i = 0; i < num1.length(); i++) {
            num1BitList[num1.length()-1-i] = num1.charAt(num1.length()-1-i)-'0';
        }


        // String num2 --> num2BitList
        int[] num2BitList = new int[num2.length()];
        for (int i = 0; i < num2.length(); i++) {
            num2BitList[num2.length()-1-i] = num2.charAt(num2.length()-1-i)-'0';
        }

        // cal num1 * num2
        for (int i = 0; i < num1.length(); i++) {
            for (int j = 0; j < num2.length(); j++) {
                res[maxResLen-1-i-j] += num1BitList[num1.length()-1-i]*num2BitList[num2.length()-1-j];
            }

        }

        // handle bit overflow
        for (int i = maxResLen-1; i >= 0; i--) {
            int tmp = res[i];
            res[i] = 0;
            int offset = 0;
            while (tmp>0){
                res[i-offset] += tmp%10;
                offset++;
                tmp/=10;
            }
        }

        // int[] res --> String
        StringBuilder sb = new StringBuilder();
        boolean beginFlag = false;
        for (int i = 0; i < maxResLen; i++) {
            if(res[i]==0&&beginFlag==false){
                continue;
            }else {
                beginFlag = true;
            }
            sb.append(res[i]);
        }
        return sb.toString();
    }


    public static void main(String[] args) {
        Solution solution = new Solution();

        String num1 = "123";
        String num2 = "456";
        String res =solution.multiply(num1,num2);
        System.out.println(res);
    }
}

2.3 提交结果

参考资料

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