leetcode-43-Multiply-Strings

描述


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

Example 1:

1
2
Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

1
2
Input: num1 = "123", num2 = "456"
Output: "56088"

Note:

  1. The length of both num1 and num2 is < 110.
  2. Both num1 and num2 contain only digits 0-9.
  3. Both num1 and num2 do not contain any leading zero, except the number 0 itself.
  4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

分析


这类题目,把小学学的乘法式写在纸上比较容易写代码。。。

1
2
3
4
5
6
7
8
  123
456
----
738
615
492
-----
56088

解决方案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
class Solution {
public String multiply(String num1, String num2) {
int num1Length = num1.length(), num2Length = num2.length();
int[] pos = new int[num1Length+num2Length];

for (int i = num1Length - 1; i >= 0; i--) {
for (int j = num2Length - 1; j >= 0; j--) {
int mulResult = (num1.charAt(i)-'0') * (num2.charAt(j)-'0');
int p1 = i + j, p2 = i + j + 1;
int sum = mulResult + pos[p2];

pos[p1] += sum / 10;
pos[p2] = sum % 10;
}
}

StringBuilder result = new StringBuilder();
for (int p: pos) {
if (!(result.length() == 0 && p == 0)) {
result.append(p);
}
}
return result.length() == 0 ? "0": result.toString();
}
}

解决方案2(Golang)


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
func multiply(num1 string, num2 string) string {
nums1Len := len(num1)
nums2Len := len(num2)
result := make([]int, nums1Len + nums2Len)

for i := nums1Len-1; i >= 0; i-- {
for j := nums2Len-1; j >= 0; j-- {
multiply := int(num1[i]-'0') * int(num2[j]-'0')
sum := result[i+j+1] + multiply
result[i+j+1] = sum % 10
result[i+j] += sum/10
}
}

start := 0
for start < nums1Len + nums2Len && result[start] == 0 {
start++
}
if start == nums1Len + nums2Len {
return "0"
}
builder := new(strings.Builder)
for i := start; i < nums1Len+nums2Len; i++ {
builder.WriteString(strconv.Itoa(result[i]))
}
return builder.String()
}

相关问题


题目来源