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
36
37
38
39
40
41
42
43
44
45 | public class Solution {
public String multiply(String num1, String num2) {
if (num1.equals("0") || num2.equals("0")) return "0";
String result = "0";
for (int i = num1.length()-1, tailZero = 0; i >= 0; i--, tailZero++){
int current = num1.charAt(i)-'0';
int carry = 0;
String temp = "";
for (int j = num2.length()-1; j >= 0; j--){
int v2 = num2.charAt(j)-'0';
int digit = (v2*current+carry)%10;
carry = (v2*current+carry)/10;
temp = digit+temp;
}
if (carry != 0) temp = carry+temp;
temp = temp + getZeros(tailZero);
result = add(result, temp);
}
return result;
}
private String getZeros(int n){
String result = "";
for (int i = 0; i < n; i++){
result += "0";
}
return result;
}
private String add(String num1, String num2){
int i = num1.length()-1;
int j = num2.length()-1;
int carry = 0;
String result = "";
while (i >= 0 || j >= 0){
int v1 = i >= 0?num1.charAt(i--)-'0':0;
int v2 = j >= 0?num2.charAt(j--)-'0':0;
int digit = (v1+v2+carry)%10;
carry = (v1+v2+carry)/10;
result = digit+result;
}
if (carry == 1) result = "1"+result;
return result;
}
}
|
No comments:
Post a Comment