LeetCode-43.字符串相乘

太过爱你忘了你带给我的痛 2022-04-25 06:52 202阅读 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）或直接将输入转换为整数来处理。

解题思路—**按位乘积**：因为题目中要求不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理，所以只能将数拆分按位乘积。  
下面举个例子来说明：123 × 12，**num中的高位从0开始**，即123的第0位为1，看下图  
![图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb3l1ZWFjZQ_size_16_color_FFFFFF_t_70]  
最上面一行multi是存储结果的数组，右边的数值是结果存放的索引值。**num1的第i位和num2的第j位相乘的结果在multi中的位置是\[i+j-1, i+j\]，因为设置multi数组的大小为num1.length+num2.length-1。** *理论上两位数相乘，数组大小应该设置为num1.length+num2.length，这里为什么可以-1，是因为乘积中最高位的进位不用再单独分出去，可以直接与最高位放在一起。* 接下来单独对每一位进行相乘，然后把结果存入相应的index中即可。

## Java解题—按位乘积 ##

class Solution {
        public String multiply(String num1, String num2) {
            if(num1==null || num1.length()==0 || num2==null || num2.length()==0)
                return "";
    
            if(num1.equals("0") || num2.equals("0"))
                return "0";
    
            // 保存最后的结果，123*9<123*10，而123*10要四位，所以123*9至多4位
            // -1是因为最高位的进位不用再单独分出去，可以直接与最高位放在一起
            int[] multi = new int[num1.length()+num2.length()-1];
            StringBuilder str = new StringBuilder();
            for(int i=num1.length()-1;i>=0;i--){
                for(int j=num2.length()-1;j>=0;j--){
                    int number1 = num1.charAt(i)-48;
                    int number2 = num2.charAt(j)-48;
    
                    // 相同位置的数合并相加
                    multi[i+j] += number1 * number2;
                    if(multi[i+j]>=10 && (i+j)!=0){
                        multi[i+j-1] += multi[i+j]/10;
                        multi[i+j] = multi[i+j]%10;
                    }
                }
            }
            for(int i=0;i<multi.length;i++)
                str.append(multi[i]);
    
            return str.toString();
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb3l1ZWFjZQ_size_16_color_FFFFFF_t_70]: /images/20220126/03e644539c0145aaafb954062a32e556.png