描述
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:
- The length of both
num1
and num2
is < 110.
- Both
num1
and num2
contain only digits 0-9
.
- Both
num1
and num2
do not contain any leading zero, except the number 0 itself.
- 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() }
|
相关问题