43. 字符串相乘

小鱼儿 2021-06-22 15:36 295阅读 0赞

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

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

**示例 2:**

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

说明：

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

**分析：**  
num1的第m位(高位从0开始)和num2的第n位相乘的结果必不大于2位，其个位放在\[m+n\]，十位放在 \[m+n+1\]  
例: 123 \* 45, 123的第0位 3 和45的第1位 4 乘积 为12 ，其十位1存放在\[2\],个位放在\[1\]中  
index: 0 1 2 3 4

1 2 3
                    *     4 5
                    ---------
                          1 5
                        1 0
                      0 5
                    ---------
                      0 6 1 5
                        1 2
                      0 8
                    0 4
                    ---------
                    0 5 5 3 5
        这样我们就可以单独都对每一位进行相乘计算把结果存入相应的index中

class Solution {
        public String multiply(String num1, String num2) {
            if(num1.equals("0") || num2.equals("0")){
                return "0";
            }else{
                char[] chars1 = num1.toCharArray();
                char[] chars2 = num2.toCharArray();
                for(int i = 0;i<chars1.length;i++){
                    chars1[i] = (char)(chars1[i] - 48);
                }
                for(int i = 0;i<chars2.length;i++){
                    chars2[i] = (char)(chars2[i] - 48);
                }
                int tmp = 0;
                //一个n位数和m位数的积必不大于m+n位
                int[] result = new int[chars1.length+chars2.length];
                for(int i = chars1.length - 1,m=0;i >= 0;i--,m++){
                    for(int j = chars2.length - 1,n=0; j >=0;j--,n++){
                        tmp = chars1[i] * chars2[j] + result[m+n]; 
                        result[m+n] = tmp % 10;
                        //满10进1
                        result[m+n+1] += tmp / 10;
                    }
                }
         
                StringBuilder sb = new StringBuilder();
                int index = result.length - 1;
                //去除高位的0
                while(result[index] == 0){
                    index--;
                }
                for(;index >= 0 ;index--){
                    sb.append(result[index]);
                }
                return sb.toString();
            }
        }
    }