LeetCode-Multiply Strings

Multiply Strings

##题目

####Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

##解题思路
该题需要知道，m和n位数的乘积，最终结果为m+n-1位或是m+n位(进位时)。乘法计算中可以发现，结果中第i位，应该由第一个字符串中的第1位乘以第二个字符串中的第i位，第一个字符串中的第2位乘以第二个字符串中的第i-1位，…….第一个字符串中的第i位乘以第二个字符串中的第1位,最后累加求得，最后我们取个位上的数值，然后剩下的作为进位放到下一轮循环中。

举个例子：

1000=1*1000 第4位=第1位*第4位
1000=10*100 第4位=第2位*第3位
1000=100*10 第4位=第3位*第2位
1000=1000*1 第4位=第4位*第1位

##算法代码
代码采用JAVA实现：

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
35
public class Solution {
    public String multiply(String num1, String num2) {
        if(num1==null || num2==null)
        	return "";
        if(num1.charAt(0)=='0')
        	return "0";
        if(num2.charAt(0)=='0')
        	return "0";
        int num1length=num1.length();
        int num2length=num2.length();
        //分别对两个开始字符串进行转置，便于后面的下标遍历
        num1=new StringBuilder(num1).reverse().toString();
        num2=new StringBuilder(num2).reverse().toString();
        StringBuilder res=new StringBuilder();
        int jinwei=0;
        //从低位开始计算，最后乘积的位数为m+n-1,如果进位则是m+n
        for(int i=0;i<num1length+num2length-1;i++)
        {
        	int multi=jinwei;
        	for(int j=0;j<=i;j++)
        	{     		
        		if(j<num1length && (i-j)<num2length)
        		{
        			multi+=(num1.charAt(j)-'0')*(num2.charAt(i-j)-'0');
        		}
        	}
        	res.append(multi%10);
        	jinwei=multi/10;
        }
        //考虑最后一位是否有进位
        if(jinwei!=0)
        	res.append(jinwei);
        return res.reverse().toString();   	
    }
}

Comments

▲