首页 > itarticle > p43

p43

admin 11月 12, 2020 0

LeetCode p43 Multiply Strings 题解

1.题目：

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

题意：

输入两个字符串，输出他们相乘的积。

2.解题思路:

用字符串模拟相乘，见代码。

3.代码

[title] [] [url] [link text]

 
public class  {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0"))
			return "0";
		StringBuilder ansBuilder = new StringBuilder();
		int len1 = num1.length();
		int len2 = num2.length();
		int[] ans = new int[len1 + len2];
		for (int i = len1 - 1; i > -1; i--) {
			for (int j = len2 - 1; j > -1; j--) {

				int a = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
				ans[i + j + 1] += a;
			}
		}
		int c = 0;
		for (int i = len1 + len2 - 1; i > -1; i--) {
			int sum = c + ans[i];
			ans[i] = sum % 10;
			c = sum / 10;
		}
		int i = 0;
		while (i < len1 + len2 && ans[i] == 0)
			i++;
		for (; i < len1 + len2; i++) {
			ansBuilder.append((char) (ans[i] + '0'));
		}
		return ansBuilder.toString();
    }
}

4.一些总结：