LeetCode43字符串相乘

发表于 | 分类于

题目：

给定两个以字符串形式表示的非负整数 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）或直接将输入转换为整数来处理。

题解

这道题就模拟我们平时做乘法的步骤就可以了。我们平时做乘法的方法的学名叫做：竖式运算（我也是刚知道这个名字）。下图就是我们所说的竖式运算方法：

  • 为了循环方便，低位放在左边，高位放在右边。即：num1 =new StringBuilder(num1).reverse().toString();
  • 两个数相乘，所乘后的数字位数最多为两数位数之和，例如：两个两位数相乘，结果最高为4位数。则需要一个长度为两数位数之和的数组，把每一位的临时结果存起来。
  • 临时结果求法：例如，12553，个位数为53=15；十位数为55+23=31；百位数为25+13=13；千位数：15=5；每一位都放在数组对应位置上，对应的代码为： d[i+j]+=ab;
  • 然后再分离个位，十位；int digit = d[i]%10;int carry = d[i]/10;d[i+1]+=carry;先把余位数字digit插入StringBuilder,sb.insert(0,digit);每次都插到第一位，因为最低位是个位，后面的是高位。
  • 最后要注意把前面的0删掉。sb.deleteCharAt(0);

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class leetcode43 {
    public String multiply(String num1,String num2){
        num1 =new StringBuilder(num1).reverse().toString();
        num2 = new StringBuilder(num2).reverse().toString();
        int[] d = new int[num1.length()+num2.length()];
        for (int i = 0; i <num1.length() ; i++) {
            int a = num1.charAt(i)- '0';
            for (int j = 0; j <num2.length() ; j++) {
                int b = num2.charAt(j)- '0';
                d[i+j]+=a*b;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i <d.length ; i++) {
            int digit = d[i]%10;
            int carry = d[i]/10;
            sb.insert(0,digit);
            if (i<d.length-1){
                d[i+1]+=carry;
            }
        }
        while (sb.length()>0 && sb.charAt(0)=='0'){
            sb.deleteCharAt(0);
        }
        return sb.length()==0?"0":sb.toString();
    }

    public static void main(String[] args) {
        String num1 ="125";
        String num2 = "53";
        leetcode43 ls =new leetcode43();
        System.out.println(ls.multiply(num1,num2));
    }
}