8000 refactor 279 · nabinkumar/Leetcode@2187651 · GitHub
[go: up one dir, main page]

Skip to content

Commit 2187651

Browse files
refactor 279
1 parent 1af7bc6 commit 2187651

File tree

1 file changed

+30
-26
lines changed
  • src/main/java/com/fishercoder/solutions

1 file changed

+30
-26
lines changed

src/main/java/com/fishercoder/solutions/_279.java

Lines changed: 30 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -3,40 +3,44 @@
33
import java.util.Arrays;
44

55
/**
6+
* 279. Perfect Squares
7+
*
68
* Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
7-
8-
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
9+
* For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
910
*/
1011
public class _279 {
11-
12-
public int numSquares(int n) {
13-
int result = n;
14-
int num = 2;
15-
while (num * num <= n) {
16-
int temp1 = n / (num * num);
17-
int temp2 = n % (num * num);
18-
result = Math.min(result, temp1 + numSquares(temp2));
19-
num++;
12+
public static class Solution1 {
13+
public int numSquares(int n) {
14+
int result = n;
15+
int num = 2;
16+
while (num * num <= n) {
17+
int temp1 = n / (num * num);
18+
int temp2 = n % (num * num);
19+
result = Math.min(result, temp1 + numSquares(temp2));
20+
num++;
21+
}
22+
return result;
2023
}
21-
return result;
2224
}
2325

24-
//DP solution
25-
public int numSquaresDP(int n) {
26-
int[] dp = new int[n + 1];
27-
Arrays.fill(dp, Integer.MAX_VALUE);
28-
dp[0] = 0;
29-
dp[1] = 1;
30-
for (int i = 1; i <= n; i++) {
31-
int min = Integer.MAX_VALUE;
32-
int j = 1;
33-
while (i - j * j >= 0) {
34-
min = Math.min(min, dp[i - j * j] + 1);
35-
j++;
26+
public static class Solution2 {
27+
//DP solution
28+
public int numSquares(int n) {
29+
int[] dp = new int[n + 1];
30+
Arrays.fill(dp, Integer.MAX_VALUE);
31+
dp[0] = 0;
32+
dp[1] = 1;
33+
for (int i = 1; i <= n; i++) {
34+
int min = Integer.MAX_VALUE;
35+
int j = 1;
36+
while (i - j * j >= 0) {
37+
min = Math.min(min, dp[i - j * j] + 1);
38+
j++;
39+
}
40+
dp[i] = min;
3641
}
37-
dp[i] = min;
42+
return dp[n];
3843
}
39-
return dp[n];
4044
}
4145

4246
}

0 commit comments

Comments
 (0)
0