|
3 | 3 | import java.util.Arrays;
|
4 | 4 |
|
5 | 5 | /**
|
| 6 | + * 279. Perfect Squares |
| 7 | + * |
6 | 8 | * 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. |
9 | 10 | */
|
10 | 11 | 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; |
20 | 23 | }
|
21 |
| - return result; |
22 | 24 | }
|
23 | 25 |
|
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; |
36 | 41 | }
|
37 |
| - dp[i] = min; |
| 42 | + return dp[n]; |
38 | 43 | }
|
39 |
| - return dp[n]; |
40 | 44 | }
|
41 | 45 |
|
42 | 46 | }
|
0 commit comments