首页 > itarticle > 字符串相乘

字符串相乘

admin 9月 30, 2020 0

题目

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

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

示例2:

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

说明：

num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

思路

翻转String。
建立数组，双层循环遍历两个string，把单位的乘积累加到数组相应的位置。
处理进位，并存入数组。
倒序遍历数组。

解答

public static String (String num1, String num2) {
    
    StringBuilder sb1 = new StringBuilder(num1).reverse();
    StringBuilder sb2 = new StringBuilder(num2).reverse();
    //字符串拆分成数组
    char[] char1 = sb1.toString().toCharArray();
    char[] char2 = sb2.toString().toCharArray();
    //创建可以容纳结果的数组
    int[] tmp = new int[char1.length + char2.length];
    //循环遍历计算每个成绩结果
    for (int i = 0; i < char1.length; i++) {
        for (int j = 0; j < char2.length; j++) {
            tmp[i + j] += ((char1[i] - '0') * (char2[j] - '0')) % 10;
            tmp[i + j + 1] += ((char1[i] - '0') * (char2[j] - '0')) / 10;
        }
    }
    //循环结果，消除余数
    for (int i = 0; i < tmp.length; i++){
        if (tmp[i] >= 10){
            tmp[i+1] += tmp[i] / 10;
            tmp[i] = tmp[i] % 10;
        }
    }
    //循环结果，查找头部多少个0，只去一个
    int count = 0;
    for (int i = tmp.length-1;i>0;i--){
        if (tmp[i]==0){
            count++;
        }else{
            break;
        }
    }
    //遍历输出结果
    StringBuilder result = new StringBuilder();
    for (int i = tmp.length-1-count;i>=0;i--){
        result.append(tmp[i]);
    }
    //返回结果
    return result.toString();

}