Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit63ebfda

Browse files
committed
043 (3) add non-reverse solution and update tests
1 parent0f07b84 commit63ebfda

File tree

4 files changed

+45
-52
lines changed

4 files changed

+45
-52
lines changed

‎src/_043_MultiplyStrings/Solution.java

Lines changed: 34 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
/**
2-
* Time : O(N*M); Space: O()
2+
* Time : O(N*M); Space: O(N + M)
33
* @tag : Math; Array
44
* @by : Steven Cooks
55
* @date: Jun 4, 2015
@@ -13,32 +13,59 @@
1313
*
1414
*************************************************************************
1515
* {@link https://leetcode.com/problems/multiply-strings/ }
16+
* @refer {@link https://leetcode.com/discuss/29364/clear-java-solution-without-reversal }
1617
*/
1718
package_043_MultiplyStrings;
1819

1920
/** see test {@link _043_MultiplyStrings.SolutionTest } */
2021
publicclassSolution {
22+
2123
publicStringmultiply(Stringnum1,Stringnum2) {
24+
StringBuildersb =newStringBuilder();
25+
int[]product =newint[num1.length() +num2.length()];
26+
for (inti =num1.length() -1;i >=0;i--) {
27+
intcarry =0;
28+
intj =num2.length() -1;
29+
intindex =i +j +1;// index where stores current result
30+
while (j >=0 ||carry !=0) {
31+
intn1 =j >=0 ?num2.charAt(j--) -'0' :0;
32+
intn2 =i >=0 ?num1.charAt(i) -'0' :0;
33+
intmulti =n1 *n2 +carry +product[index];
34+
carry =multi /10;
35+
product[index--] =multi %10;
36+
}
37+
}
38+
booleanobvious =false;// first non-zero digit
39+
for (inti =0;i <product.length;i++) {
40+
if (product[i] ==0 && !obvious) {
41+
continue;
42+
}
43+
obvious =true;
44+
sb.append(product[i]);
45+
}
46+
returnsb.length() ==0 ?"0" :sb.toString();
47+
}
48+
49+
// version2: need a reverse at the end
50+
publicStringmultiply_reverse(Stringnum1,Stringnum2) {
2251
intlen1 =num1.length();
2352
intlen2 =num2.length();
24-
// pre-allocate
2553
int[]product =newint[len1 +len2];
2654
for (inti =len1 -1;i >=0;i--) {
2755
for (intj =len2 -1;j >=0;j--) {
2856
intindex =len1 +len2 -i -j -2;
29-
product[index] += (num1.charAt(i) -'0')
30-
* (num2.charAt(j) -'0');
57+
product[index] += (num1.charAt(i) -'0') * (num2.charAt(j) -'0');
3158
product[index +1] +=product[index] /10;
3259
product[index] %=10;
3360
}
3461
}
35-
3662
StringBuilderstringBuilder =newStringBuilder();
37-
for (inti =product.length -1;i >=0;i--) {
38-
if (i >0 &&stringBuilder.length() ==0 &&product[i] ==0)
63+
for (inti =product.length -1;i >0;i--) {
64+
if (stringBuilder.length() ==0 &&product[i] ==0)
3965
continue;
4066
stringBuilder.append(product[i]);
4167
}
68+
stringBuilder.append(product[0]);
4269
returnstringBuilder.toString();
4370
}
4471

‎src/_043_MultiplyStrings/SolutionBigInteger.java

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -18,12 +18,14 @@
1818

1919
importjava.math.BigInteger;
2020

21-
/** see test {@link _043_MultiplyStrings.SolutionBigIntegerTest} */
21+
/** see test {@link _043_MultiplyStrings.SolutionBigIntegerTest} */
2222
publicclassSolutionBigInteger {
23+
2324
publicStringmultiply(Stringnum1,Stringnum2) {
2425
// cheating way: use BigInteger class in Java
2526
BigIntegerb1 =newBigInteger(num1);
2627
BigIntegerb2 =newBigInteger(num2);
2728
returnb1.multiply(b2).toString();
2829
}
30+
2931
}

‎test/_043_MultiplyStrings/PracticeTest.java

Lines changed: 4 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -45,26 +45,8 @@ public void Test2() {
4545
assertEquals(expected,actual);
4646
}
4747

48-
// @Test
49-
// public void Test3() {
50-
// String num1 = "2";
51-
// String num2 = "-2";
52-
// String actual = solution.multiply(num1, num2);
53-
// String expected = "-4";
54-
// assertEquals(expected, actual);
55-
// }
56-
//
57-
// @Test
58-
// public void Test4() {
59-
// String num1 = "-1";
60-
// String num2 = "-2";
61-
// String actual = solution.multiply(num1, num2);
62-
// String expected = "2";
63-
// assertEquals(expected, actual);
64-
// }
65-
6648
@Test
67-
publicvoidTest5() {
49+
publicvoidTest3() {
6850
Stringnum1 ="100000";
6951
Stringnum2 ="200000";
7052
Stringactual =solution.multiply(num1,num2);
@@ -73,7 +55,7 @@ public void Test5() {
7355
}
7456

7557
@Test
76-
publicvoidTest6() {
58+
publicvoidTest4() {
7759
Stringnum1 ="15";
7860
Stringnum2 ="15";
7961
Stringactual =solution.multiply(num1,num2);
@@ -82,7 +64,7 @@ public void Test6() {
8264
}
8365

8466
@Test
85-
publicvoidTest7() {
67+
publicvoidTest5() {
8668
Stringnum1 ="30000";
8769
Stringnum2 ="40000";
8870
Stringactual =solution.multiply(num1,num2);
@@ -91,7 +73,7 @@ public void Test7() {
9173
}
9274

9375
@Test
94-
publicvoidTest8() {
76+
publicvoidTest6() {
9577
Stringnum1 ="93553535314";
9678
Stringnum2 ="25247452591474";
9779
Stringactual =solution.multiply(num1,num2);

‎test/_043_MultiplyStrings/SolutionTest.java

Lines changed: 4 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -45,26 +45,8 @@ public void Test2() {
4545
assertEquals(expected,actual);
4646
}
4747

48-
// @Test
49-
// public void Test3() {
50-
// String num1 = "2";
51-
// String num2 = "-2";
52-
// String actual = solution.multiply(num1, num2);
53-
// String expected = "-4";
54-
// assertEquals(expected, actual);
55-
// }
56-
//
57-
// @Test
58-
// public void Test4() {
59-
// String num1 = "-1";
60-
// String num2 = "-2";
61-
// String actual = solution.multiply(num1, num2);
62-
// String expected = "2";
63-
// assertEquals(expected, actual);
64-
// }
65-
6648
@Test
67-
publicvoidTest5() {
49+
publicvoidTest3() {
6850
Stringnum1 ="100000";
6951
Stringnum2 ="200000";
7052
Stringactual =solution.multiply(num1,num2);
@@ -73,7 +55,7 @@ public void Test5() {
7355
}
7456

7557
@Test
76-
publicvoidTest6() {
58+
publicvoidTest4() {
7759
Stringnum1 ="15";
7860
Stringnum2 ="15";
7961
Stringactual =solution.multiply(num1,num2);
@@ -82,7 +64,7 @@ public void Test6() {
8264
}
8365

8466
@Test
85-
publicvoidTest7() {
67+
publicvoidTest5() {
8668
Stringnum1 ="30000";
8769
Stringnum2 ="40000";
8870
Stringactual =solution.multiply(num1,num2);
@@ -91,7 +73,7 @@ public void Test7() {
9173
}
9274

9375
@Test
94-
publicvoidTest8() {
76+
publicvoidTest6() {
9577
Stringnum1 ="93553535314";
9678
Stringnum2 ="25247452591474";
9779
Stringactual =solution.multiply(num1,num2);

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp